https://doi.org/10.26089/NumMet.v27r216

Parallel algorithm for finding a regularized solution to ill-conditioned systems of linear algebraic equations with adaptive accounting for round-off errors

Authors

  • Valentin D. Shinkarev
  • Akim M. Zlatkovskii
  • Dmitry V. Lukyanenko

Keywords:

ill-posed problem
regularizing algorithm
conjugate gradient method
round-off errors
parallelization
MPI

Abstract

The paper discusses the construction of parallel algorithms and their software implementation for solving ill-posed linear inverse problems. Such problems often reduce to solving large overdetermined systems of linear algebraic equations (SLAEs) with dense matrices. These inverse problems are addressed using regularizing algorithms, a key step of which involves selecting the regularization parameter. In computationally challenging multidimensional inverse problems, the accuracy of the regularized solution can be critically affected by round-off errors accumulated during the computation. Incorporating an estimate of these accumulated errors into the procedure for selecting the regularization parameter can enhance the accuracy of the resulting solution. However, it may also significantly limit the scalability of the corresponding parallel software implementation. This work compares the capabilities of various standards of the Message Passing Interface parallel programming technology to solve the problem of partial compensation for additional computing and communication costs associated with accounting for round-off errors. Examples of the proposed algorithm’s implementation are provided using the Python programming language and the mpi4py package, with their structure designed for straightforward adaptation to C/C++/Fortran.


Downloads

Published

2026-05-26

Issue

Vol. 27 (2026): Issue 2.

Section

Parallel software tools and technologies

Authors

Valentin D. Shinkarev

Lomonosov Moscow State University, Faculty of Physics

• PhD Student

Akim M. Zlatkovskii

Lomonosov Moscow State University, Faculty of Physics

• Student

Dmitry V. Lukyanenko

Lomonosov Moscow State University, Faculty of Physics

• Associate Professor, Deputy Head of Department

References

  1. Vl. V. Voevodin, A. S. Antonov, D. A. Nikitenko, et al., “Supercomputer Lomonosov-2: Large Scale, Deep Monitoring and Fine Analytics for the User Community,” Supercomputing Frontiers and Innovations 6 (2), 4–11 (2019).
    doi 10.14529/jsfi190201
  2. A. N. Tikhonov, A. V. Goncharsky, V. V. Stepanov, and A. G. Yagola, Numerical Methods for The Solution of Ill-Posed Problems(Kluwer Academic Publishers, Dordrecht, 1995).
    doi 10.1007/978-94-015-8480-7
  3. M. R. Hestenes and E. Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems,” Journal of Research of the National Bureau of Standards 49 (6), 409–436 (1952).
  4. Z. Strakoš, “On the Real Convergence Rate of the Conjugate Gradient Method,” Linear Algebra and Its Applications 154, 535–549 (1991).
    doi 10.1016/0024-3795(91)90393-B
  5. H. Woźniakowski, “Roundoff-Error Analysis of a New Class of Conjugate-Gradient Algorithms,” Linear Algebra and Its Applications 29, 507–529 (1980).
  6. E. F. Kaasschieter, “A Practical Termination Criterion for the Conjugate Gradient Method,” BIT Numerical Mathematics 28 (2), 308–322 (1988).
    doi 10.1007/BF01934094
  7. M. Arioli, I. Duff, and D. Ruiz, “Stopping Criteria for Iterative Solvers,” SIAM Journal on Matrix Analysis and Applications 13 (1), 138–144 (1992).
    doi 10.1137/0613012
  8. Y. Notay, “On the Convergence Rate of the Conjugate Gradients in Presence of Rounding Errors,” Numerische Mathematik 65 (1), 301–317 (1993).
    doi 10.1007/BF01385754
  9. O. Axelsson and I. Kaporin, “Error Norm Estimation and Stopping Criteria in Preconditioned Conjugate Gradient Iterations,” Numerical Linear Algebra with Applications 8 (4), 265–286 (2001).
    doi 10.1002/nla.244
  10. Z. Strakoš and P. Tich’y, “On Error Estimation in the Conjugate Gradient Method and Why It Works in Finite Precision Computations,” Electronic Transactions on Numerical Analysis 13, 56–80 (2002).
  11. G. Meurant, The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations (SIAM, 2006).
  12. X.-W. Chang, C. C. Paige and D. Titley-Peloquin, “Stopping Criteria for the Iterative Solution of Linear Least Squares Problems,” SIAM Journal on Matrix Analysis and Applications 31 (2), 831–852 (2009).
    doi 10.1137/080724071
  13. P. Jiránek, Z. Strakoš, and M. Vohralík, “A Posteriori Error Estimates Including Algebraic Error and Stopping Criteria for Iterative Solvers,” SIAM Journal on Scientific Computing 32 (3), 1567–1590 (2010).
    doi 10.1137/08073706X
  14. S. Cools, E. F. Yetkin, E. Agullo, et al., “Analyzing the Effect of Local Rounding Error Propagation on the Maximal Attainable Accuracy of the Pipelined Conjugate Gradient Method,” SIAM Journal on Matrix Analysis and Applications 39 (1), 426–450 (2018).
    doi 10.1137/17M1117872
  15. A. Greenbaum, H. Liu, and T. Chen, “On the Convergence Rate of Variants of the Conjugate Gradient Algorithm in Finite Precision Arithmetic,” SIAM Journal on Scientific Computing 43 (5), S496–S515 (2021).
    doi 10.1137/20M1346249
  16. D. V. Lukyanenko, V. D. Shinkarev, and A. G. Yagola, “Accounting for Round-Off Errors When Using Gradient Minimization Methods,” Algorithms 15 (9), Article Number 324 (2022).
    doi 10.3390/a15090324
  17. D. V. Lukyanenko, “Parallel Algorithm for Solving Overdetermined Systems of Linear Equations, Taking into Account Round-Off Errors,” Algorithms 16 (5), Article Number 242 (2023).
    doi 10.3390/a16050242
  18. L. Dalcin and Y.-L. L. Fang, “mpi4py: Status Update After 12 Years of Development,” Computing in Science & Engineering 23 (4), 47–54 (2021).
    doi 10.1109/MCSE.2021.3083216
  19. M. Rogowski, S. Aseeri, D. Keyes, and L. Dalcin, “mpi4py.futures: MPI-Based Asynchronous Task Execution for Python,” IEEE Transactions on Parallel and Distributed Systems 34 (2), 611–622 (2023).
    doi 10.1109/TPDS.2022.3225481
  20. J. W. Demmel, M. T. Heath, and H. A. Van Der Vorst, “Parallel Numerical Linear Algebra,” Acta Numerica 2, 111–197 (1993).
    doi 10.1017/S096249290000235X
  21. P. R. Eller and W. Gropp, “Scalable Non-Blocking Preconditioned Conjugate Gradient Methods,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’16), Salt Lake City, UT, USA, November 13–18, 2016 (IEEE Press, 2016), pp. 204-215.
    doi 10.1109/SC.2016.17
  22. D. V. Lukyanenko, S. S. Torbin, and V. D. Shinkarev, “How to Parallelize &quotNon-Parallelizable&quot Minimization Functions,” Lobachevskii Journal of Mathematics 46 (8), 3725–3740 (2025).
    doi 10.1134/S199508022560997X
  23. A. S. Antonov, Vl. V. Voevodin, and D. V. Lukyanenko, “Supercomputing Co-Design for Solving Ill-Posed Linear Inverse Problems Using Iterative Algorithms,” Supercomputing Frontiers and Innovations 12 (4), 16–33 (2025).
    doi 10.14529/jsfi250402

License

Copyright (c) 2026 В. Д. Шинкарев, A. M. Златковский, Д. В. Лукьяненко

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.