Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 15

Proceedings of the 2018 Federated Conference on Computer Science and Information Systems

A New Monte Carlo Algorithm for Linear Algebraic Systems Based on the ``Walk on Equations'' Algorithm

, , ,

DOI: http://dx.doi.org/10.15439/2018F121

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 257–260 ()

Full text

Abstract. A new Monte Carlo algorithm for solving systems of Linear Algebraic (LA) equations is presented and studied. The algorithm is based on the ``Walk on Equations'' Monte Carlo method recently developed by Ivan Dimov, Sylvain Maire and Jean Michel Sellier. The algorithm is optimized by choosing the appropriate values for the relaxation parameters which leads to dramatic reduction in time and lower relative errors for a given number of iterations. Numerical tests are performed for examples with matrices of different size and on a system coming from a finite element approximation of a problem describing a beam structure in constructive mechanics.

References

  1. Curtiss, J.H., Monte Carlo methods for the iteration of linear operators, J. Math Phys., Vol. 32(4), 209–232, 1954, http://dx.doi.org/10.1002/sapm1953321209.
  2. Dimov, I., Optimal Monte Carlo Algorithms, Proceedings IEEE John Vincent Atanasoff 2006 International Symposium on Modern Computing, October 2006, Sofia, Bulgaria, IEEE, Los Alamitos, California, 125–131, 2006, http://dx.doi.org/10.1109/JVA.2006.37.
  3. Dimov, I., Monte Carlo Methods for Applied Scientists, New Jersey, London, Singapore, World Scientific, 291p, 2008.
  4. Dimov, I. T., S. Maire, J.M. Sellier, A New Walk on Equations Monte Carlo Method for Linear Algebraic Problems, Applied Mathematical Modelling, Vol. 39(15), 4494–4510, 2015, DOI: 10.1016/j.apm.2014.12.018.
  5. Golub, G. H., Van Loon C.F., Matrix computations, Third Edition, Johns Hopkins Univ. Press, Baltimore, 1996.
  6. Halton, J., Sequential Monte Carlo, Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 58(1), 57–78, 1962, http://dx.doi.org/10.1017/S0305004100036227.
  7. NOS4: Lanczos with partial reorthogonalization. Finite element approximation to a beam structure. http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/lanpro/nos4.html
  8. Errors for Linear Systems: http://www.math.umd.edu/petersd/466/linsysterrn.pdf