Iterative Monte Carlo algorithms for linear algebra problems

A common Monte Carlo approach for linear algebra problems is presented. The considered problems are inverting a matrix B, solving systems of linear algebraic equations of the form Bu=b and calculating eigenvalues of symmetric matrices. Several algorithms using the same Markov chains with different random variables are described.The presented algorithms contain iterations with a resolvent matrix (used as iterative operator) of a given matrix. For inverting matrices and solving linear systems a mapping of the spectral parameter domain of convergence is established. This transformation leads to a new resolvent matrix and, respectively, to a new random variable constructed on the corresponding Markov chain, which allows the use of smaller number of iterations for reaching a given error. For calculating of eigenvalues an additional parameter in resolvent operator is involved to accelerate the algorithm convergence. The convergence of the iterative processes is proved and the convergence rate is compared with the rate of existing Monte Carlo algorithms for similar problems.An error analysis is done.Numerical experiments for Monte Carlo Almost Optimal (MAO) algorithms are performed on CRAY Y-MP C92A. It is shown that the accuracy and the algorithm complexity practically does not depend on the size of the matrix.