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

Bai, Zhong-Zhi

doi:10.1090/S0025-5718-05-01801-6

Structured preconditioners for nonsingular matrices of block two-by-two structures
HTML articles powered by AMS MathViewer

by Zhong-Zhi Bai;

Math. Comp. 75 (2006), 791-815

DOI: https://doi.org/10.1090/S0025-5718-05-01801-6

Published electronically: November 30, 2005

HTML | PDF | Request permission

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

Habib Ammari, Gang Bao, and Aihua W. Wood, An integral equation method for the electromagnetic scattering from cavities, Math. Methods Appl. Sci. 23 (2000), no. 12, 1057–1072. MR 1773922, DOI 10.1002/1099-1476(200008)23:12<1057::AID-MMA151>3.0.CO;2-6
Owe Axelsson, Iterative solution methods, Cambridge University Press, Cambridge, 1994. MR 1276069, DOI 10.1017/CBO9780511624100
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)
Zhongzhi Bai, A class of hybrid algebraic multilevel preconditioning methods, Appl. Numer. Math. 19 (1996), no. 4, 389–399. MR 1377785, DOI 10.1016/0168-9274(95)00106-9
Zhong-Zhi Bai, Parallel hybrid algebraic multilevel iterative methods, Linear Algebra Appl. 267 (1997), 281–315. MR 1479124, DOI 10.1016/S0024-3795(97)00024-4
Zhong-Zhi Bai, A class of modified block SSOR preconditioners for symmetric positive definite systems of linear equations, Adv. Comput. Math. 10 (1999), no. 2, 169–186. MR 1680610, DOI 10.1023/A:1018974514896
Zhong-Zhi Bai, Mofidied block SSOR preconditioners for symmetric positive definite linear systems, Ann. Oper. Res. 103 (2001), 263–282. Optimization and numerical algebra (Nanjing, 1999). MR 1868455, DOI 10.1023/A:1012915424955
Zhong-Zhi Bai, Iain S. Duff, and Andrew J. Wathen, A class of incomplete orthogonal factorization methods. I. Methods and theories, BIT 41 (2001), no. 1, 53–70. MR 1829661, DOI 10.1023/A:1021913700691
Zhong-Zhi Bai and Gui-Qing Li, Restrictively preconditioned conjugate gradient methods for systems of linear equations, IMA J. Numer. Anal. 23 (2003), no. 4, 561–580. MR 2011340, DOI 10.1093/imanum/23.4.561
Z.-Z. Bai and M.K. Ng, On inexact preconditioners for nonsymmetric matrices, SIAM J. Sci. Comput., 26(2005), 1710-1724.
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.
Zhongzhi Bai and Deren Wang, A class of new hybrid algebraic multilevel preconditioning methods, Linear Algebra Appl. 260 (1997), 223–255. MR 1448358, DOI 10.1016/S0024-3795(97)80012-2
John T. Betts, Practical methods for optimal control using nonlinear programming, Advances in Design and Control, vol. 3, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. MR 1826768
Åke Björck, Numerical methods for least squares problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1386889, DOI 10.1137/1.9781611971484
James H. Bramble, Joseph E. Pasciak, and Apostol T. Vassilev, Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal. 34 (1997), no. 3, 1072–1092. MR 1451114, DOI 10.1137/S0036142994273343
Franco Brezzi and Michel Fortin, Mixed and hybrid finite element methods, Springer Series in Computational Mathematics, vol. 15, Springer-Verlag, New York, 1991. MR 1115205, DOI 10.1007/978-1-4612-3172-1
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), no. 2, 181–204. MR 1105227, DOI 10.1093/imanum/11.2.181
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), no. 2, 227–257. MR 1408491, DOI 10.1145/229473.229480
Nira Dyn and Warren E. Ferguson Jr., The numerical solution of equality constrained quadratic programming problems, Math. Comp. 41 (1983), no. 163, 165–170. MR 701631, DOI 10.1090/S0025-5718-1983-0701631-X
Stanley C. Eisenstat, Howard C. Elman, and Martin H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal. 20 (1983), no. 2, 345–357. MR 694523, DOI 10.1137/0720023
Howard C. Elman, Preconditioners for saddle point problems arising in computational fluid dynamics, Appl. Numer. Math. 43 (2002), no. 1-2, 75–89. 19th Dundee Biennial Conference on Numerical Analysis (2001). MR 1936103, DOI 10.1016/S0168-9274(02)00118-6
Howard C. Elman and Gene H. Golub, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal. 31 (1994), no. 6, 1645–1661. MR 1302679, DOI 10.1137/0731085
Howard C. Elman, David J. Silvester, and Andrew J. Wathen, Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations, Numer. Math. 90 (2002), no. 4, 665–688. MR 1888834, DOI 10.1007/s002110100300
B. Fischer, A. Ramage, D. J. Silvester, and A. J. Wathen, Minimum residual methods for augmented systems, BIT 38 (1998), no. 3, 527–543. MR 1652781, DOI 10.1007/BF02510258
Philip E. Gill, Walter Murray, and Margaret H. Wright, Practical optimization, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1981. MR 634376
Roland Glowinski, Numerical methods for nonlinear variational problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984. MR 737005, DOI 10.1007/978-3-662-12613-4
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
Gene H. Golub and Andrew J. Wathen, An iteration for indefinite systems and its application to the Navier-Stokes equations, SIAM J. Sci. Comput. 19 (1998), no. 2, 530–539. MR 1618828, DOI 10.1137/S106482759529382X
Gene H. Golub, X. Wu, and Jin-Yun Yuan, SOR-like methods for augmented systems, BIT 41 (2001), no. 1, 71–85. MR 1829662, DOI 10.1023/A:1021965717530
Nicholas I. M. Gould, Mary E. Hribar, and Jorge Nocedal, On the solution of equality constrained quadratic programming problems arising in optimization, SIAM J. Sci. Comput. 23 (2001), no. 4, 1376–1395. MR 1885606, DOI 10.1137/S1064827598345667
Eldad Haber, Uri M. Ascher, and Doug Oldenburg, On optimization techniques for solving nonlinear inverse problems, Inverse Problems 16 (2000), no. 5, 1263–1280. Electromagnetic imaging and inversion of the Earth’s subsurface. MR 1798355, DOI 10.1088/0266-5611/16/5/309
Apostolos Hadjidimos, Accelerated overrelaxation method, Math. Comp. 32 (1978), no. 141, 149–157. MR 483340, DOI 10.1090/S0025-5718-1978-0483340-6
Jianming Jin, The finite element method in electromagnetics, 2nd ed., Wiley-Interscience [John Wiley & Sons], New York, 2002. MR 1903357
Carsten Keller, Nicholas I. M. Gould, and Andrew J. Wathen, Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl. 21 (2000), no. 4, 1300–1317. MR 1780274, DOI 10.1137/S0895479899351805
Axel Klawonn, Block-triangular preconditioners for saddle point problems with a penalty term, SIAM J. Sci. Comput. 19 (1998), no. 1, 172–184. Special issue on iterative methods (Copper Mountain, CO, 1996). MR 1616885, DOI 10.1137/S1064827596303624
Peter A. Markowich, The stationary semiconductor device equations, Computational Microelectronics, Springer-Verlag, Vienna, 1986. MR 821965, DOI 10.1007/978-3-7091-3678-2
Malcolm F. Murphy, Gene H. Golub, and Andrew J. Wathen, A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput. 21 (2000), no. 6, 1969–1972. MR 1762024, DOI 10.1137/S1064827599355153
I. Perugia and V. Simoncini, Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations, Numer. Linear Algebra Appl. 7 (2000), no. 7-8, 585–616. Preconditioning techniques for large sparse matrix problems in industrial applications (Minneapolis, MN, 1999). MR 1802361, DOI 10.1002/1099-1506(200010/12)7:7/8<585::AID-NLA214>3.3.CO;2-6
Robert J. Plemmons, A parallel block iterative scheme applied to computations in structural analysis, SIAM J. Algebraic Discrete Methods 7 (1986), no. 3, 337–347. MR 844035, DOI 10.1137/0607038
Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
Youcef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856–869. MR 848568, DOI 10.1137/0907058
Guido E. Sartoris, A 3D rectangular mixed finite element method to solve the stationary semiconductor equations, SIAM J. Sci. Comput. 19 (1998), no. 2, 387–403. MR 1618875, DOI 10.1137/S1064827594275091
S. Selberherr, Analysis and Simulation of Semiconductor Devices, Springer-Verlag, New York, 1984.
Gilbert Strang, Introduction to applied mathematics, Wellesley-Cambridge Press, Wellesley, MA, 1986. MR 870634
Walter Zulehner, Analysis of iterative methods for saddle point problems: a unified approach, Math. Comp. 71 (2002), no. 238, 479–505. MR 1885611, DOI 10.1090/S0025-5718-01-01324-2