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

Параллельный алгоритм поиска регуляризованного решения плохо обусловленных СЛАУ с адаптивным учетом ошибок машинного округления

Авторы

  • В. Д. Шинкарев
  • A. M. Златковский
  • Д. В. Лукьяненко

Ключевые слова:

некорректно поставленная задача
регуляризирующий алгоритм
метод сопряжённых градиентов
ошибки машинного округления
распараллеливание
MPI

Аннотация

В работе обсуждаются особенности построения параллельных алгоритмов и их программной реализации для решения некорректно поставленных линейных обратных задач, которые сводятся к необходимости решения больших переопределенных систем линейных алгебраических уравнений с плотно заполненной матрицей. Такие обратные задачи решаются с использованием регуляризирующих алгоритмов, одним из этапов реализации которых является выбор параметра регуляризации. В вычислительно сложных многомерных обратных задачах на точность регуляризованного решения могут оказывать критическое влияние ошибки машинного округления, накапливающиеся в процессе счета. Включение оценки накопленных ошибок машинного округления в процедуру выбора параметра регуляризации позволяет повысить точность полученного регуляризованного решения, однако может существенно ограничить масштабируемость соответствующей параллельной программной реализации алгоритма. В работе сравниваются возможности различных стандартов технологии параллельного программирования Message Passing Interface по решению проблемы частичной компенсации дополнительных вычислительных и коммуникационных затрат, связанных с учетом ошибок машинного округления. Приводятся примеры реализации предложенного алгоритма на языке программирования Python с использованием пакета mpi4py, структура которых ориентирована на простую адаптацию для языков C/C++/Fortran.


Загрузки

Опубликован

2026-05-26

Выпуск

Том 27 (2026): Выпуск 2.

Раздел

Параллельные программные средства и технологии

Авторы

В. Д. Шинкарев

Московский государственный университет имени М.В. Ломоносова, физический факультет

• аспирант

A. M. Златковский

Московский государственный университет имени М.В. Ломоносова, физический факультет

• студент

Д. В. Лукьяненко

Московский государственный университет имени М.В. Ломоносова, физический факультет

• доцент,  заместитель заведующего кафедрой

Библиографические ссылки

  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

Лицензия

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

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.