Reusing Random Walks in Monte Carlo Methods for Linear Systems

In this paper, we present an approach of reusing random walks in Monte Carlo methods for linear systems. The fundamental idea is, during the Monte Carlo sampling process, the random walks generated to estimate one unknown element can also be effectively reused to estimate the other unknowns in the solution vector. As a result, when the random walks are reused, a single random walk can contribute samples for estimations of multiple unknowns in the solution simultaneously while ensuring that the samples for the same unknown element are statistically independent. Consequently, the total number of random walk transition steps needed for estimating the overall solution vector is reduced, which improves the performance of the Monte Carlo algorithm. We apply this approach to the Monte Carlo algorithm in two linear algebra applications, including solving a system of linear equations and approximating the inversion of a matrix. Our computational results show that compared to the conventional implementations of Monte Carlo algorithms for linear systems without random walk reusing, our approach can significantly improve the performance of Monte Carlo sampling process by reducing the overall number of transition steps in random walks to obtain the entire solution within desired precision.