A New Monte Carlo Algorithm for Linear Algebraic Systems Based on the ``Walk on Equations'' Algorithm
Venelin Todorov, Nikolay Ikonomov, Ivan Dimov, Rayna Georgieva
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 (2018)
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
- 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.
- 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.
- Dimov, I., Monte Carlo Methods for Applied Scientists, New Jersey, London, Singapore, World Scientific, 291p, 2008.
- 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.
- Golub, G. H., Van Loon C.F., Matrix computations, Third Edition, Johns Hopkins Univ. Press, Baltimore, 1996.
- 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.
- NOS4: Lanczos with partial reorthogonalization. Finite element approximation to a beam structure. http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/lanpro/nos4.html
- Errors for Linear Systems: http://www.math.umd.edu/petersd/466/linsysterrn.pdf