Abstract
Randomized scalable vector algorithms for calculation of matrix iterations and solving extremely large linear algebraic equations are developed. Among applications presented in this paper are randomized iterative methods for large linear systems of algebraic equations governed by M-matrices. The crucial idea of the randomized method is that the iterations are performed by sampling random columns only, thus avoiding not only matrix-matrix but also matrix-vector multiplications. The suggested vector randomized methods are highly efficient for solving linear equations of high dimension, the computational cost depends only linearly on the dimension.
Funding source: Russian Science Foundation
Award Identifier / Grant number: 19-11-00019
Funding source: Russian Foundation for Basic Research
Award Identifier / Grant number: 20-51-18009
Funding statement: The work is supported by the Russian Science Foundation, Grant 19-11-00019, in the part of stochastic simulation theory development, and by the Russian Fund of Basic Research, under Grant 20-51-18009, in the part of randomized algorithms implementation.
References
[1] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Revised reprint of the 1979 original, Class. Appl. Math. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1994. 10.1137/1.9781611971262Search in Google Scholar
[2] S. M. Ermakov and G. A. Mikhaĭlov, Statistical Simulation (in Russian), 2nd ed., “Nauka”, Moscow, 1982. Search in Google Scholar
[3] K. K. Sabelfeld, First passage Monte Carlo algorithms for solving coupled systems of diffusion–reaction equations, Appl. Math. Lett. 88 (2019), 141–148. 10.1016/j.aml.2018.08.018Search in Google Scholar
[4] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995. 10.1017/CBO9780511814075Search in Google Scholar
[5] D. Noutsos, On Perron-Frobenius property of matrices having some negative entries, Linear Algebra Appl. 412 (2006), no. 2–3, 132–153. 10.1016/j.laa.2005.06.037Search in Google Scholar
[6] G. N. Položiĭ, A method of solution of integral equations, Izv. Akad. Nauk SSSR. Ser. Mat. 23 (1959), 295–312. Search in Google Scholar
[7] K. Sabelfeld, Monte Carlo Methods in Boundary Value Problems, Springer Ser. Computat. Phys., Springer, Berlin, 1991. 10.1007/978-3-642-75977-2Search in Google Scholar
[8] K. Sabelfeld, Stochastic algorithms in linear algebra—beyond the Markov chains and von Neumann–Ulam scheme, Numerical Methods and Applications, Lecture Notes in Comput. Sci. 6046, Springer, Heidelberg (2011), 14–28. 10.1007/978-3-642-18466-6_2Search in Google Scholar
[9] K. Sabelfeld, Random walk on spheres algorithm for solving transient drift-diffusion-reaction problems, Monte Carlo Methods Appl. 23 (2017), no. 3, 189–212. 10.1515/mcma-2017-0113Search in Google Scholar
[10] K. Sabelfeld, Stochastic simulation algorithms for solving narrow escape diffusion problems by introducing a drift to the target, J. Comput. Phys. 410 (2020), Article ID 109406. 10.1016/j.jcp.2020.109406Search in Google Scholar
[11] K. Sabelfeld, V. Kaganer, C. Pfueller and O. Brandt, Dislocation contrast in cathodoluminescence and electron-beam induced current maps on GaN(0001), J. Phys. D 50 (2017), no. 40, Article ID 405101. Search in Google Scholar
[12] K. Sabelfeld and N. Loshchina, Stochastic iterative projection methods for large linear systems, Monte Carlo Methods Appl. 16 (2010), no. 3–4, 343–359. 10.1515/mcma.2010.020Search in Google Scholar
[13] K. Sabelfeld and N. S. Mozartova, Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation, Math. Comput. Simulation 82 (2011), no. 2, 295–317. 10.1016/j.matcom.2011.08.002Search in Google Scholar
[14] T. Strohmer and R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl. 15 (2009), no. 2, 262–278. 10.1007/s00041-008-9030-4Search in Google Scholar
[15] P. Tarazaga, M. Raydan and A. Hurman, Perron-Frobenius theorem for matrices with some negative entries, Linear Algebra Appl. 328 (2001), no. 1–3, 57–68. 10.1016/S0024-3795(00)00327-XSearch in Google Scholar
[16] A. J. Walker, New fast method for generating discrete random numbers with arbitrary frequency distributions, Electronic Lett. 10 (1974), 127–128. 10.1049/el:19740097Search in Google Scholar
© 2022 Walter de Gruyter GmbH, Berlin/Boston