Time complexity of sequential and parallel Monte Carlo solution of linear equations

Description

The Monte Carlo method proposed by von Neumann and Ulam for solving linear equations is considered in this paper. It is shown that the primary estimate computation processes in this method can be viewed as the realizations of an absorbing Markov chain. Subsequently, the time complexity analysis of the algorithm is carried out using some results from the absorbing Markov chain theory. Two techniques, proper transition probability assignments and the truncation of random walks, are discussed for the time complexity reduction. Finally, the various schemes recently presented for the development of parallel Monte Carlo algorithms are shown to be applicable in implementing the method on parallel computers. It is shown that the time complexity of the method for estimating the solutions of a system of Ν linear equations on Ν·Κ processors, using Κ primary estimates for each of the unknowns, is independent of N.