Enhanced Monte Carlo Techniques for Solving Linear Systems

Abstract A novel hybrid Monte Carlo algorithm for solving systems of linear algebraic equations is introduced and evaluated in this study. This algorithm builds on the recent “Walk on Equations” Monte Carlo method developed by Ivan Dimov, Sylvain Maire, and Jean Michel Sellier. For the first time, this approach has been compared with the Gauss-Seidel method for matrices of big size. Significant improvements have been made to the algorithm by selecting optimal values for the relaxation parameters, resulting in a considerable reduction in computational time and lower relative errors across a specified number of iterations. The convergence of the algorithm has been rigorously established through a new theorem. It has been demonstrated that the original algorithm can be optimized by properly balancing the iteration matrix. Additionally, a sequential Monte Carlo method developed by John Halton, which utilizes the control variate method iteratively, has also been implemented.