Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Structured preconditioners for nonsingular matrices of block two-by-two structures

Author: Zhong-Zhi Bai
Journal: Math. Comp. 75 (2006), 791-815
MSC (2000): Primary 65F10, 65F50
Published electronically: November 30, 2005
MathSciNet review: 2196992
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For the large sparse block two-by-two real nonsingular matrices, we establish a general framework of practical and efficient structured preconditioners through matrix transformation and matrix approximations. For the specific versions such as modified block Jacobi-type, modified block Gauss-Seidel-type, and modified block unsymmetric (symmetric) Gauss-Seidel-type preconditioners, we precisely describe their concrete expressions and deliberately analyze eigenvalue distributions and positive definiteness of the preconditioned matrices. Also, we show that when these structured preconditioners are employed to precondition the Krylov subspace methods such as GMRES and restarted GMRES, fast and effective iteration solvers can be obtained for the large sparse systems of linear equations with block two-by-two coefficient matrices. In particular, these structured preconditioners can lead to efficient and high-quality preconditioning matrices for some typical matrices from the real-world applications.

References [Enhancements On Off] (What's this?)

  • 1. H. Ammari, G. Bao and A.W. Wood,
    An integral equation method for the electromagnetic scattering from cavities,
    Math. Methods Appl. Sci., 23(2000), 1057-1072. MR 1773922 (2001g:78013)
  • 2. O. Axelsson,
    Iterative Solution Methods,
    Cambridge University Press, Cambridge, 1994. MR 1276069 (95f:65005)
  • 3. Z.-Z. Bai,
    Parallel Iterative Methods for Large-Scale Systems of Algebraic Equations,
    Ph.D. Thesis of Shanghai University of Science and Technology, Shanghai, June 1993. (In Chinese)
  • 4. Z.-Z. Bai,
    A class of hybrid algebraic multilevel preconditioning methods,
    Appl. Numer. Math., 19(1996), 389-399. MR 1377785 (96j:65116)
  • 5. Z.-Z. Bai,
    Parallel hybrid algebraic multilevel iterative methods,
    Linear Algebra Appl., 267(1997), 281-315.MR 1479124 (99c:65081)
  • 6. Z.-Z. Bai,
    A class of modified block SSOR preconditioners for symmetric positive definite systems of linear equations,
    Adv. Comput. Math., 10(1999), 169-186.MR 1680610 (2000c:65020)
  • 7. Z.-Z. Bai,
    Modified block SSOR preconditioners for symmetric positive definite linear systems,
    Ann. Operations Research, 103(2001), 263-282.MR 1868455 (2002k:65046)
  • 8. Z.-Z. Bai, I.S. Duff and A.J. Wathen,
    A class of incomplete orthogonal factorization methods. I: methods and theories,
    BIT, 41(2001), 53-70. MR 1829661 (2002b:65040)
  • 9. Z.-Z. Bai and G.-Q. Li,
    Restrictively preconditioned conjugate gradient methods for systems of linear equations,
    IMA J. Numer. Anal., 23(2003), 561-580. MR 2011340 (2004i:65025)
  • 10. Z.-Z. Bai and M.K. Ng,
    On inexact preconditioners for nonsymmetric matrices,
    SIAM J. Sci. Comput., 26(2005), 1710-1724.
  • 11. Z.-Z. Bai and Z.-Q. Wang,
    Restrictive preconditioners for conjugate gradient methods for symmetric positive definite linear systems,
    J. Comput. Appl. Math., 187(2006), 202-226.
  • 12. Z.-Z. Bai and D.-R. Wang,
    A class of new hybrid algebraic multilevel preconditioning methods,
    Linear Algebra Appl., 260(1997), 223-255. MR 1448358 (98i:65035)
  • 13. J.T. Betts,
    Practical Methods for Optimal Control Using Nonlinear Programming,
    SIAM, Philadelphia, PA, 2001. MR 1826768 (2002e:49001)
  • 14. A. Björck,
    Numerical Methods for Least Squares Problems,
    SIAM, Philadelphia, PA, 1996. MR 1386889 (97g:65004)
  • 15. J.H. Bramble, J.E. Pasciak and A.T. Vassilev,
    Analysis of the inexact Uzawa algorithm for saddle point problems,
    SIAM J. Numer. Anal., 34(1997), 1072-1092. MR 1451114 (98c:65182)
  • 16. F. Brezzi and M. Fortin,
    Mixed and Hybrid Finite Element Methods,
    Springer-Verlag, New York, 1991.MR 1115205 (92d:65187)
  • 17. I.S. Duff, N.I.M. Gould, J.K. Reid, J.A. Scott and K. Turner,
    The factorization of sparse symmetric indefinite matrices,
    IMA J. Numer. Anal., 11(1991), 181-204. MR 1105227 (92a:65143)
  • 18. I.S. Duff and J.K. Reid,
    Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems,
    ACM Trans. Math. Software, 22(1996), 227-257. MR 1408491 (97c:65085)
  • 19. N. Dyn and W.E. Ferguson, Jr.,
    The numerical solution of equality constrained quadratic programming problems,
    Math. Comput., 41(1983), 165-170. MR 0701631 (85b:90051)
  • 20. S.C. Eisenstat, H.C. Elman and M.H. Schultz,
    Variational iterative methods for nonsymmetric systems of linear equations,
    SIAM J. Numer. Anal., 20(1983), 345-357.MR 0694523 (84h:65030)
  • 21. H.C. Elman,
    Preconditioners for saddle point problems arising in computational fluid dynamics,
    Appl. Numer. Math., 43(2002), 75-89. MR 1936103
  • 22. H.C. Elman and G.H. Golub,
    Inexact and preconditioned Uzawa algorithms for saddle point problems,
    SIAM J. Numer. Anal., 31(1994), 1645-1661. MR 1302679 (95f:65065)
  • 23. H.C. Elman, D.J. Silvester and A.J. Wathen,
    Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations,
    Numer. Math., 90(2002), 665-688.MR 1888834 (2002m:76071)
  • 24. B. Fischer, R. Ramage, D.J. Silvester and A.J. Wathen,
    Minimum residual methods for augmented systems,
    BIT, 38(1998), 527-543.MR 1652781 (99i:65031)
  • 25. P.E. Gill, W. Murray and M.H. Wright,
    Practical Optimization,
    Academic Press, New York, NY, 1981.MR 0634376 (83d:65195)
  • 26. R. Glowinski,
    Numerical Methods for Nonlinear Variational Problems,
    Springer-Verlag, New York, 1984.MR 0737005 (86c:65004)
  • 27. G.H. Golub and C.F. Van Loan,
    Matrix Computations, 3rd Edition,
    The Johns Hopkins University Press, Baltimore and London, 1996.MR 1417720 (97g:65006)
  • 28. G.H. Golub and A.J. Wathen,
    An iteration for indefinite systems and its application to the Navier-Stokes equations,
    SIAM J. Sci. Comput., 19(1998), 530-539.MR 1618828 (99d:65107)
  • 29. G.H. Golub, X. Wu and J.-Y. Yuan,
    SOR-like methods for augmented systems,
    BIT, 41(2001), 71-85.MR 1829662 (2002a:65055)
  • 30. N.I.M. Gould, M.E. Hribar and J. Nocedal,
    On the solution of equality constrained quadratic programming problems arising in optimization,
    SIAM J. Sci. Comput., 23(2001), 1375-1394.MR 1885606 (2002k:90072)
  • 31. E. Haber, U.M. Ascher and D. Oldenburg,
    On optimization techniques for solving nonlinear inverse problems,
    Inverse Problems, 16(2000), 1263-1280.MR 1798355 (2001j:78025)
  • 32. A. Hadjidimos,
    Accelerated overrelaxation method,
    Math. Comput., 32(1978), 149-157.MR 0483340 (58:3353)
  • 33. J. Jin,
    The Finite Element Method in Electromagnetics,
    John Wiley & Sons, New York, NY, 1993.MR 1903357 (2004b:78019)
  • 34. C. Keller, N.I.M. Gould and A.J. Wathen,
    Constrained preconditioning for indefinite linear systems,
    SIAM J. Matrix Anal. Appl., 21(2000), 1300-1317.MR 1780274 (2002b:65050)
  • 35. A. Klawonn,
    Block-triangular preconditioners for saddle point problems with a penalty term,
    SIAM J. Sci. Comput., 19(1998), 172-184.MR 1616885 (99f:65051)
  • 36. P.A. Markowich,
    The Stationary Semiconductor Device Equations,
    Springer-Verlag, New York, 1986.MR 0821965 (87b:78042)
  • 37. M.F. Murphy, G.H. Golub and A.J. Wathen,
    A note on preconditioning for indefinite linear systems,
    SIAM J. Sci. Comput., 21(2000), 1969-1972.MR 1762024 (2001a:65055)
  • 38. I. Perugia and V. Simoncini,
    Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations,
    Numer. Linear Algebra Appl., 7(2000), 585-616.MR 1802361 (2001j:65187)
  • 39. R.J. Plemmons,
    A parallel block iterative method applied to computations in structural analysis,
    SIAM J. Alg. Disc. Meth., 7(1986), 337-347.MR 0844035 (88h:49058)
  • 40. Y. Saad,
    Iterative Methods for Sparse Linear Systems, 2nd Edition,
    SIAM, Philadelphia, PA, 2003. MR 1990645 (2004h:65002)
  • 41. Y. Saad and M.H. Schultz,
    GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems,
    SIAM J. Sci. Stat. Comput., 7(1986), 856-869.MR 0848568 (87g:65064)
  • 42. G.E. Sartoris,
    A 3D rectangular mixed finite element method to solve the stationary semiconductor equations,
    SIAM J. Sci. Stat. Comput., 19(1998), 387-403.MR 1618875 (99b:65147)
  • 43. S. Selberherr,
    Analysis and Simulation of Semiconductor Devices,
    Springer-Verlag, New York, 1984.
  • 44. G. Strang,
    Introduction to Applied Mathematics,
    Wellesley-Cambridge Press, MA, 1986.MR 0870634 (88a:00006)
  • 45. W. Zulenher,
    Analysis of iterative methods for saddle point problems: a unified approach,
    Math. Comput., 71(2001), 479-505.MR 1885611 (2003f:65183)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65F10, 65F50

Retrieve articles in all journals with MSC (2000): 65F10, 65F50

Additional Information

Zhong-Zhi Bai
Affiliation: State Key Laboratory of Scientific/Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, P.O. Box 2719, Beijing 100080, People’s Republic of China

Keywords: Block two-by-two matrix, preconditioner, modified block relaxation iteration, eigenvalue distribution, positive definiteness
Received by editor(s): October 16, 2003
Received by editor(s) in revised form: March 16, 2005
Published electronically: November 30, 2005
Additional Notes: Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803), The National Basic Research Program (No. 2005CB321702), and The National Natural Science Foundation (No. 10471146), P.R. China
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society