CGMN Revisited: Robust and Efficient Solution of Stiff Linear Systems Derived from Elliptic Partial Differential Equations

ABSTRACT

Given a linear system Ax  =  b, one can construct a related “normal equations” system AA^Ty = b, x = A^Ty. Björck 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.

REFERENCES

• 1: Mario Arioli , Iain Duff , Joseph Noailles , Daniel Ruiz, A block projection method for sparse matrices, SIAM Journal on Scientific and Statistical Computing, v.13 n.1, p.47-70, Jan. 1992 [doi>10.1137/0913003]
• 2: Mario Arioli , Iain S. Duff , Daniel Ruiz , Miloud Sadkane, Block Lanczos techniques for accelerating the block Cimmino method, SIAM Journal on Scientific Computing, v.16 n.6, p.1478-1511, Nov. 1995 [doi>10.1137/0916086]
• 3: Björck, Å. and Elfving, T. 1979. Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations. BIT 19, 145--163.
• 4: R. Bramley , H.-C. Chen , U. Meier , A. Sameh, On some parallel preconditioned CG schemes, Proceedings of a conference on Preconditioned conjugate gradient methods, p.17-27, January 1991, Nijmegen, The Netherlands
• 5: R. Bramley , A. Sameh, Domain decomposition for parallel row projection algorithms, Applied Numerical Mathematics, v.8 n.4-5, p.303-315, Nov 1991 [doi>10.1016/0168-9274(91)90071-7]
• 6: R. Bramley , A. Sameh, Row projection methods for large nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.13 n.1, p.168-193, Jan. 1992 [doi>10.1137/0913010]
• 7: Cimmino, G. 1938. Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. La Ricerca Scientifica XVI, Series II, Anno IX 1, 326--333.
• 8: Eggermont, P. P. B., Herman, G. T., and Lent, A. 1981. Iterative algorithms for large partitioned linear systems, with applications to image reconstruction. Linear Alg. Appl. 40, 37--67.
• 9: Elfving, T. 1980. Block-iterative methods for consistent and inconsistent linear equations. Numerische Mathematik 35, 1--12.
• 10: Elfving, T. 2004. A projection method for semidefinite linear systems and its applications. Linear Alg. Appl. 391, 57--73.
• 11: Elman, H. and Golub, G. 1990. Iterative methods for cyclically reduced non-self-adjoint linear systems. Math. Comput. 54, 190 (Apr.), 671--700.
• 12: José-Jesús Fernández , Dan Gordon , Rachel Gordon, Efficient parallel implementation of iterative reconstruction algorithms for electron tomography, Journal of Parallel and Distributed Computing, v.68 n.5, p.626-640, May, 2008 [doi>10.1016/j.jpdc.2007.09.003]
• 13: Ferziger, J. H. and Perić, M. 2002. Computational Methods for Fluid Dynamics, 3rd. ed. Springer-Verlag, Berlin.
• 14: Fletcher, R. 1976. Conjugate gradient methods for indefinite systems. In Proceedings of the Dundee Biennial Conference on Numerical Analysis. G. A. Watson, Ed. Lecture Notes in Mathematics, vol. 506. Springer-Verlag, Berlin, 73--89.
• 15: Dan Gordon , Rachel Gordon, Component-Averaged Row Projections: A Robust, Block-Parallel Scheme for Sparse Linear Systems, SIAM Journal on Scientific Computing, v.27 n.3, p.1092-1117, 2005 [doi>10.1137/040609458]
• 16: 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.
• 17: Gordon, D. and Mansour, R. 2007. A geometric approach to quadratic optimization: an improved method for solving strongly underdetermined systems in CT. Inverse Prob. Sci. Eng. 15, 8 (Dec.), 811--826.
• 18: Gresho, P. and Sani, R. 1998. Incompressible Flow and the Finite Element Method: Advection-Diffusion and Isothermal Laminar Flow. John Wiley & Sons, Ltd., Chichester, England.
• 19: Herman, G. T. 1980. Image Reconstruction From Projections: The Fundamentals of Computerized Tomography. Academic Press, New York.
• 20: Gabor T. Herman , Arnold Lent , Peter H. Lutz, Relaxation methods for image reconstruction, Communications of the ACM, v.21 n.2, p.152-158, Feb. 1978 [doi>10.1145/359340.359351]
• 21: Hestenes, M. R. and Stiefel, E. 1952. Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Stand. 49, 409--436.
• 22: Kaczmarz, S. 1937. Angenäherte Auflösung von Systemen linearer Gleichungen. Bulletin de l’Académie Polonaise des Sciences et Lettres A35, 355--357.
• 23: Kamath, C. and Sameh, A. 1989. A projection method for solving non-symmetric linear systems on multi processors. Para. Comput. 9, 3, 291--312.
• 24: Kamath, C. and Weeratunga, S. 1990. Implementation of two projection methods on a shared memory multiprocessor: DEC VAX 6240. Para. Comput. 16, 375--382.
• 25: Kamath, C. and Weeratunga, S. 1992. Projection methods for the numerical solution of non-self-adjoint elliptic partial differential equations. Numer. Meth. Partial Diff. Equat. 8, 59--76.
• 26: 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.
• 27: Kuck, D., Davidson, E., Lawrie, D., and Sameh, A. 1986. Parallel super-computing today and the cedar approach. Science 231, 967--974.
• 28: Lanczos, C. 1952. Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bur. Stand. 49, 33--53.
• 29: Saad, Y. 1990. SPARSKIT: a basic tool kit for sparse matrix computations. Tech. Rep. RIACS-90-20, Research Institute for Advanced Computer Science, NASA Ames Research Center, Moffet Field, CA.
• 30: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 31: Youcef Saad , Martin H Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.856-869, July 1986 [doi>10.1137/0907058]
• 32: Peter Sonneveld, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.10 n.1, p.36-52, January 1989 [doi>10.1137/0910004]
• 33: Tanabe, K. 1971. Projection method for solving a singular system of linear equations and its applications. Numerische Mathematik 17, 203--214.
• 34: Trummer, M. R. 1981. Reconstructing pictures from projections: On the convergence of the ART algorithm with relaxation. Computing 26, 189--195.
• 35: Tuminaro, R. S., Heroux, M. A., Hutchinson, S. A., and Shadid, J. N. 1999. AZTEC user’s guide. Tech. Rep. SAND99-8801J, Sandia National Laboratories, Albuquerque, New Mexico.
• 36: H. A. van der Vorst, BI-CGSTAB: a fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.13 n.2, p.631-644, March 1992 [doi>10.1137/0913035]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Stability (and instability)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods); Linear systems (direct and iterative methods)
      G.1.8 Partial Differential Equations
          Subjects: Iterative solution techniques
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness

Keywords:
CGMN, CGNR, Kaczmarz, SOR, SSOR, conjugate-gradient, convection-dominated, elliptic equations, linear systems, normal equations, partial differential equations, row projections, sparse linear systems, stiff equations