{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T03:53:24Z","timestamp":1768017204583,"version":"3.49.0"},"reference-count":29,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2023,5,7]],"date-time":"2023-05-07T00:00:00Z","timestamp":1683417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Russian Science Foundation","award":["23-41-00002"],"award-info":[{"award-number":["23-41-00002"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The paper proposes a parallel algorithm for solving large overdetermined systems of linear algebraic equations with a dense matrix. This algorithm is based on the use of a modification of the conjugate gradient method, which is able to take into account rounding errors accumulated during calculations when making a decision to terminate the iterative process. The parallel algorithm is constructed in such a way that it takes into account the capabilities of the message passing interface (MPI) parallel programming technology, which is used for the software implementation of the proposed algorithm. The programming examples are shown using the Python programming language and the mpi4py package, but all programs are built in such a way that they can be easily rewritten using the C\/C++\/Fortran programming languages. The advantage of using the modern MPI-4.0 standard is demonstrated.<\/jats:p>","DOI":"10.3390\/a16050242","type":"journal-article","created":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T02:03:31Z","timestamp":1683511411000},"page":"242","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Parallel Algorithm for Solving Overdetermined Systems of Linear Equations, Taking into Account Round-Off Errors"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5140-3617","authenticated-orcid":false,"given":"Dmitry","family":"Lukyanenko","sequence":"first","affiliation":[{"name":"Department of Mathematics, Faculty of Physics, Lomonosov Moscow State University, Moscow 119991, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2023,5,7]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1017\/S096249290000235X","article-title":"Parallel numerical linear algebra","volume":"2","author":"Demmel","year":"1993","journal-title":"Acta Numer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"409","DOI":"10.6028\/jres.049.044","article-title":"Methods of conjugate gradients for solving linear systems","volume":"49","author":"Hestenes","year":"1952","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Greenbaum, A. (1997). Iterative Methods For Solving Linear Systems, SIAM.","DOI":"10.1137\/1.9781611970937"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Kabanikhin, S. (2011). Inverse and Ill-Posed Problems: Theory and Applications, Walter de Gruyter.","DOI":"10.1515\/9783110224016"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1016\/0024-3795(80)90259-1","article-title":"Roundoff-error analysis of a new class of conjugate-gradient algorithms","volume":"29","year":"1980","journal-title":"Linear Algebra Its Appl."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1007\/BF01934094","article-title":"A practical termination criterion for the conjugate gradient method","volume":"28","author":"Kaasschieter","year":"1988","journal-title":"BIT Numer. Math."},{"key":"ref_7","first-page":"535","article-title":"On the real convergence rate of the conjugate gradient method","volume":"154","year":"1991","journal-title":"Linear Algebra Its Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1137\/0613012","article-title":"Stopping Criteria for Iterative Solvers","volume":"13","author":"Arioli","year":"1992","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01385754","article-title":"On the convergence rate of the conjugate gradients in presence of rounding errors","volume":"65","author":"Notay","year":"1993","journal-title":"Numer. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1002\/nla.244","article-title":"Error norm estimation and stopping criteria in preconditioned conjugate gradient iterations","volume":"8","author":"Axelsson","year":"2001","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s100920170006","article-title":"Stopping criteria for iterative methods: Applications to PDE\u2019s","volume":"38","author":"Arioli","year":"2001","journal-title":"Calcolo"},{"key":"ref_12","first-page":"56","article-title":"On error estimation in the conjugate gradient method and why it works in finite precision computations","volume":"13","year":"2002","journal-title":"Electron. Trans. Numer. Anal."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00211-003-0500-y","article-title":"A stopping criterion for the conjugate gradient algorithm in a finite element method framework","volume":"97","author":"Arioli","year":"2004","journal-title":"Numer. Math."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Meurant, G. (2006). The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations, SIAM.","DOI":"10.1137\/1.9780898718140"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1137\/080724071","article-title":"Stopping Criteria for the Iterative Solution of Linear Least Squares Problems","volume":"31","author":"Chang","year":"2009","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1567","DOI":"10.1137\/08073706X","article-title":"A posteriori error estimates including algebraic error and stopping criteria for iterative solvers","volume":"32","year":"2010","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.apnum.2016.03.006","article-title":"A stopping criterion for iterative regularization methods","volume":"106","author":"Landi","year":"2016","journal-title":"Appl. Numer. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.jcp.2017.09.033","article-title":"A stopping criterion for the iterative solution of partial differential equations","volume":"352","author":"Rao","year":"2018","journal-title":"J. Comput. Phys."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"A3549","DOI":"10.1137\/16M1103361","article-title":"The Numerical Stability Analysis of Pipelined Conjugate Gradient Methods: Historical Context and Methodology","volume":"40","author":"Carson","year":"2018","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1137\/17M1117872","article-title":"Analyzing the effect of local rounding error propagation on the maximal attainable accuracy of the pipelined conjugate gradient method","volume":"39","author":"Cools","year":"2018","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"S496","DOI":"10.1137\/20M1346249","article-title":"On the Convergence Rate of Variants of the Conjugate Gradient Algorithm in Finite Precision Arithmetic","volume":"43","author":"Greenbaum","year":"2021","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_22","unstructured":"Polyak, B., Kuruzov, I., and Stonyakin, F. (2022). Stopping Rules for Gradient Methods for Non-Convex Problems with Additive Noise in Gradient. arXiv."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Lukyanenko, D., Shinkarev, V., and Yagola, A. (2022). Accounting for round-off errors when using gradient minimization methods. Algorithms, 15.","DOI":"10.3390\/a15090324"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/0168-9274(95)00079-A","article-title":"Reducing the effect of global communication in GMRES(m) and CG on parallel distributed memory computers","volume":"18","year":"1995","journal-title":"Appl. Numer. Math."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Eller, P.R., and Gropp, W. (2016, January 13\u201318). Scalable non-blocking preconditioned conjugate gradient methods. Proceedings of the SC\u201916: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Salt Lake City, UT, USA.","DOI":"10.1109\/SC.2016.17"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"DAzevedo, E., and Romine, C. (1992). Reducing Communication Costs in the Conjugate Gradient Algorithm on Distributed Memory Multiprocessors, Oak Ridge National Lab.. Technical Report.","DOI":"10.2172\/7172467"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Dongarra, J.J., Duff, I.S., Sorensen, D.C., and Van der Vorst, H.A. (1998). Numerical Linear Algebra for High-Performance Computers, SIAM.","DOI":"10.1137\/1.9780898719611"},{"key":"ref_28","first-page":"4","article-title":"Supercomputer Lomonosov-2: Large Scale, Deep Monitoring and Fine Analytics for the User Community","volume":"6","author":"Voevodin","year":"2019","journal-title":"Supercomput. Front. Innov."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Tikhonov, A., Goncharsky, A., Stepanov, V., and Yagola, A. (1995). Numerical Methods for the Solution of Ill-Posed Problems, Kluwer Academic Publishers.","DOI":"10.1007\/978-94-015-8480-7"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/5\/242\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:30:45Z","timestamp":1760124645000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/5\/242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,7]]},"references-count":29,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2023,5]]}},"alternative-id":["a16050242"],"URL":"https:\/\/doi.org\/10.3390\/a16050242","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,7]]}}}