Logo PTI Logo FedCSIS

Proceedings of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 47

An Optimized Modified Walk on Equations Monte Carlo Algorithm for Large Sparse Linear Systems

, ,

DOI: http://dx.doi.org/10.15439/2026F9246

Citation: Venelin Todorov, ,

Full text

Abstract. This paper investigates stochastic Walk on Equations (WE) methods for the numerical solution of linear algebraic systems and proposes an optimized modified WE algorithm aimed at large sparse matrices. Building on the classical WE Monte Carlo framework and its more recent modified version, we reformulate the main computational procedures, compare their algorithmic structure, and discuss their suitability for large-scale problems. To the best of our knowledge, this is the first study in the present setting that explicitly directs the WE methodology toward large sparse linear systems and interprets the modified construction as the basis for a new optimized stochastic solver. The paper considers the classical WE method, the modified WE method, and standard stationary iterative schemes, namely Jacobi and Gauss--Seidel. Their behavior is examined through numerical experiments for systems of dimensions n = 500 and n = 1000, where the relative error is analyzed as a function of the iteration number. The obtained results show that the modified WE algorithm consistently outperforms the classical WE approach and both deterministic benchmarks in terms of convergence speed and final accuracy. In particular, the new method exhibits a significantly faster decay of the relative error and preserves its favorable behavior as the dimension increases. These findings indicate that the modified WE framework is not merely a reformulation of the original stochastic scheme, but a practically more effective Monte Carlo strategy. The reported results also suggest that it provides a promising foundation for the development of optimized algorithms for large sparse linear systems, where efficiency, scalability, and controlled trajectory behavior are of primary importance.

References

  1. Curtiss, J.H.: Monte Carlo methods for the iteration of linear operators. Journal of Mathematics and Physics 32(4), 209–232 (1954)
  2. Curtiss, J.H.: A theoretical comparison of the efficiencies of two classical methods and a Monte Carlo method for computing one component of the solution of a set of linear algebraic equations. In: Proceedings of the Symposium on Monte Carlo Methods, John Wiley and Sons, 191–233 (1956)
  3. Dimov, I.T., Maire, S., Sellier, J.M.: A New Walk on Equations Monte Carlo Method for Linear Algebraic Problems. Applied Mathematical Modelling 39(15), 4494–4510 (2015)
  4. Dimov, I., Tonev, O.: Performance Analysis of Monte Carlo Algorithms for Some Models of Computer Architectures. In: International Youth Workshop on Monte Carlo Methods and Parallel Algorithms – Primorsko, eds. Bl. Sendov, I. Dimov, World Scientific, Singapore, 91–95 (1990)
  5. Halton, J.: Sequential Monte Carlo. Proceedings of the Cambridge Philosophical Society 58, 57–78 (1962)
  6. Halton, J.: Sequential Monte Carlo. University of Wisconsin, Madison, Mathematics Research Center Technical Summary Report No. 816 (1967)
  7. Halton, J., Zeidman, E.A.: Monte Carlo integration with sequential stratification. University of Wisconsin, Madison, Computer Science Department Technical Report No. 61 (1969)
  8. Halton, J.: Sequential Monte Carlo for linear systems – a practical summary. Monte Carlo Methods and Applications 14, 1–27 (2008)
  9. Maire, S.: Reducing variance using iterated control variates. Journal of Statistical Computation and Simulation 73(1), 1–29 (2003)
  10. Spanier, J., Gelbard, E.: Monte Carlo Principles and Neutron Transport Problem. Addison–Wesley (1969)