{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T13:49:56Z","timestamp":1778680196169,"version":"3.51.4"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,10,1]],"date-time":"2008-10-01T00:00:00Z","timestamp":1222819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2008,10]]},"abstract":"<jats:p>\n            Given a linear system\n            <jats:italic>Ax<\/jats:italic>\n            \u2009=\u2009\n            <jats:italic>b<\/jats:italic>\n            , one can construct a related \u201cnormal equations\u201d system\n            <jats:italic>AA<\/jats:italic>\n            <jats:sup>T<\/jats:sup>\n            <jats:italic>y<\/jats:italic>\n            \u2009=\u2009\n            <jats:italic>b, x<\/jats:italic>\n            \u2009=\u2009\n            <jats:italic>A<\/jats:italic>\n            <jats:sup>T<\/jats:sup>\n            <jats:italic>y<\/jats:italic>\n            . Bj\u00f6rck and Elfving have shown that the SSOR algorithm, applied to the normal equations, can be accelerated by the conjugate gradient algorithm (CG). The resulting algorithm, called CGMN, is error-reducing and in theory it always converges even when the equation system is inconsistent and\/or nonsquare. SSOR on the normal equations is equivalent to the Kaczmarz algorithm (KACZ), with a fixed relaxation parameter, run in a double (forward and backward) sweep on the original equations. CGMN was tested on nine well-known large and sparse linear systems obtained by central-difference discretization of elliptic convection-diffusion partial differential equations (PDEs). Eight of the PDEs were strongly convection-dominated, and these are known to produce very stiff systems with large off-diagonal elements. CGMN was compared with some of the foremost state-of-the art Krylov subspace methods: restarted GMRES, Bi-CGSTAB, and CGS. These methods were tested both with and without various preconditioners. CGMN converged in all the cases, while none of the preceding algorithm\/preconditioner combinations achieved this level of robustness. Furthermore, on varying grid sizes, there was only a gradual increase in the number of iterations as the grid was refined. On the eight convection-dominated cases, the initial convergence rate of CGMN was better than all the other combinations of algorithms and preconditioners, and the residual decreased monotonically. The CGNR algorithm was also tested, and it was as robust as CGMN, but slower.\n          <\/jats:p>","DOI":"10.1145\/1391989.1391991","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T13:49:43Z","timestamp":1225979383000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["CGMN Revisited"],"prefix":"10.1145","volume":"35","author":[{"given":"Dan","family":"Gordon","sequence":"first","affiliation":[{"name":"University of Haifa"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rachel","family":"Gordon","sequence":"additional","affiliation":[{"name":"Technion-Israel Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0913003"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0916086"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01930845"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Conference on Preconditioned Conjugate Gradient Methods","volume":"1457","author":"Bramley R.","unstructured":"Bramley , R. , Chen , H.-C. , Meier , U. , and Sameh , A . 1990. On some parallel preconditioned CG schemes . In Proceedings of the International Conference on Preconditioned Conjugate Gradient Methods . Nijmegen, The Netherlands, (June) O. Axelsson and L. Yu. Kolotilina, Eds. Lecture Notes in Mathematics , vol. 1457 . Springer-Verlag, Berlin, 17--27. Bramley, R., Chen, H.-C., Meier, U., and Sameh, A. 1990. On some parallel preconditioned CG schemes. In Proceedings of the International Conference on Preconditioned Conjugate Gradient Methods. Nijmegen, The Netherlands, (June) O. Axelsson and L. Yu. Kolotilina, Eds. Lecture Notes in Mathematics, vol. 1457. Springer-Verlag, Berlin, 17--27."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-9274(91)90071-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0913010"},{"key":"e_1_2_1_7_1","first-page":"326","article-title":"Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. La Ricerca Scientifica XVI, Series II","author":"Cimmino G.","year":"1938","unstructured":"Cimmino , G. 1938 . Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. La Ricerca Scientifica XVI, Series II , Anno IX 1, 326 -- 333 . Cimmino, G. 1938. Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. La Ricerca Scientifica XVI, Series II, Anno IX 1, 326--333.","journal-title":"Anno"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(81)90139-7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396365"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.11.025"},{"key":"e_1_2_1_11_1","first-page":"190","article-title":"Iterative methods for cyclically reduced non-self-adjoint linear systems","volume":"54","author":"Elman H.","year":"1990","unstructured":"Elman , H. and Golub , G. 1990 . Iterative methods for cyclically reduced non-self-adjoint linear systems . Math. Comput. 54 , 190 (Apr.), 671--700. Elman, H. and Golub, G. 1990. Iterative methods for cyclically reduced non-self-adjoint linear systems. Math. Comput. 54, 190 (Apr.), 671--700.","journal-title":"Math. Comput."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.09.003"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Ferziger J. H. and Peri\u0107 M. 2002. Computational Methods for Fluid Dynamics 3rd. ed. Springer-Verlag Berlin. Ferziger J. H. and Peri\u0107 M. 2002. Computational Methods for Fluid Dynamics 3rd. ed. Springer-Verlag Berlin.","DOI":"10.1007\/978-3-642-56026-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0080116"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/040609458"},{"key":"e_1_2_1_16_1","unstructured":"Gordon D. and Gordon R. 2008. CARP-CG: a robust and efficient parallel solver for linear systems applied to strongly convection-dominated elliptic partial differential equations. To appear. Gordon D. and Gordon R. 2008. CARP-CG: a robust and efficient parallel solver for linear systems applied to strongly convection-dominated elliptic partial differential equations. To appear."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/17415970600952078"},{"key":"e_1_2_1_18_1","unstructured":"Gresho P. and Sani R. 1998. Incompressible Flow and the Finite Element Method: Advection-Diffusion and Isothermal Laminar Flow. John Wiley &amp; Sons Ltd. Chichester England. Gresho P. and Sani R. 1998. Incompressible Flow and the Finite Element Method: Advection-Diffusion and Isothermal Laminar Flow . John Wiley &amp; Sons Ltd. Chichester England."},{"key":"e_1_2_1_19_1","volume-title":"Image Reconstruction From Projections: The Fundamentals of Computerized Tomography","author":"Herman G. T.","unstructured":"Herman , G. T. 1980. Image Reconstruction From Projections: The Fundamentals of Computerized Tomography . Academic Press , New York . Herman, G. T. 1980. Image Reconstruction From Projections: The Fundamentals of Computerized Tomography. Academic Press, New York."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359351"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"e_1_2_1_22_1","unstructured":"Kaczmarz S. 1937. Angen\u00e4herte Aufl\u00f6sung von Systemen linearer Gleichungen. Bulletin de l\u2019Acad\u00e9mie Polonaise des Sciences et Lettres A35 355--357. Kaczmarz S. 1937. Angen\u00e4herte Aufl\u00f6sung von Systemen linearer Gleichungen. Bulletin de l\u2019Acad\u00e9mie Polonaise des Sciences et Lettres A35 355--357."},{"key":"e_1_2_1_23_1","first-page":"291","article-title":"A projection method for solving non-symmetric linear systems on multi processors. Para","volume":"9","author":"Kamath C.","year":"1989","unstructured":"Kamath , C. and Sameh , A. 1989 . A projection method for solving non-symmetric linear systems on multi processors. Para . Comput. 9 , 3, 291 -- 312 . Kamath, C. and Sameh, A. 1989. A projection method for solving non-symmetric linear systems on multi processors. Para. Comput. 9, 3, 291--312.","journal-title":"Comput."},{"key":"e_1_2_1_24_1","first-page":"375","article-title":"Implementation of two projection methods on a shared memory multiprocessor: DEC VAX 6240. Para","volume":"16","author":"Kamath C.","year":"1990","unstructured":"Kamath , C. and Weeratunga , S. 1990 . Implementation of two projection methods on a shared memory multiprocessor: DEC VAX 6240. Para . Comput. 16 , 375 -- 382 . Kamath, C. and Weeratunga, S. 1990. Implementation of two projection methods on a shared memory multiprocessor: DEC VAX 6240. Para. Comput. 16, 375--382.","journal-title":"Comput."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/num.1690080104"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Kincaid D. and Young D. 1981. Adapting iterative algorithms developed for symmetric systems to non-symmetric systems. In Elliptic Problem Solvers M. Schultz Ed. Academic Press New York 353--359. Kincaid D. and Young D. 1981. Adapting iterative algorithms developed for symmetric systems to non-symmetric systems. In Elliptic Problem Solvers M. Schultz Ed. Academic Press New York 353--359.","DOI":"10.1016\/B978-0-12-632620-8.50033-4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.231.4741.967"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.006"},{"key":"e_1_2_1_30_1","volume-title":"2nd. ed","author":"Saad Y.","unstructured":"Saad , Y. 2003. Iterative Methods for Sparse Linear Systems , 2nd. ed . SIAM , Philadelphia, PA . Saad, Y. 2003. Iterative Methods for Sparse Linear Systems, 2nd. ed. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0910004"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436376"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02243477"},{"key":"e_1_2_1_35_1","volume-title":"Tech. Rep. SAND99-8801J, Sandia National Laboratories","author":"Tuminaro R. S.","year":"1999","unstructured":"Tuminaro , R. S. , Heroux , M. A. , Hutchinson , S. A. , and Shadid , J. N . 1999 . AZTEC user\u2019s guide. Tech. Rep. SAND99-8801J, Sandia National Laboratories , Albuquerque, New Mexico . Tuminaro, R. S., Heroux, M. A., Hutchinson, S. A., and Shadid, J. N. 1999. AZTEC user\u2019s guide. Tech. Rep. SAND99-8801J, Sandia National Laboratories, Albuquerque, New Mexico."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0913035"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391989.1391991","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1391989.1391991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:58:05Z","timestamp":1750255085000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391989.1391991"}},"subtitle":["Robust and Efficient Solution of Stiff Linear Systems Derived from Elliptic Partial Differential Equations"],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1145\/1391989.1391991"],"URL":"https:\/\/doi.org\/10.1145\/1391989.1391991","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10]]},"assertion":[{"value":"2007-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}