×
Bai, Zhong-Zhi

Structured preconditioners for nonsingular matrices of block two-by-two structures. (English) Zbl 1091.65041

Math. Comput. 75, No. 254, 791-815 (2006).
Author’s 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 generalized minimal residual (GMRES) methods 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.
Reviewer: Dietrich Braess (Bochum)

Cited in 203 Documents

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices

Keywords:

preconditioner; generalized minimal residual (GMRES) methods; large sparse systems; preconditioning; block Jacobi-type preconditioner; block Gauss-Seidel type preconditioner
Cite Review PDF
Full Text: DOI

References:

[1] 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. , https://doi.org/10.1002/1099-1476(200008)23:123.0.CO;2-6 · Zbl 0991.78012
[2] Owe Axelsson, Iterative solution methods, Cambridge University Press, Cambridge, 1994. · Zbl 0795.65014
[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] Zhongzhi Bai, A class of hybrid algebraic multilevel preconditioning methods, Appl. Numer. Math. 19 (1996), no. 4, 389 – 399. · Zbl 0855.65029 · doi:10.1016/0168-9274(95)00106-9
[5] Zhong-Zhi Bai, Parallel hybrid algebraic multilevel iterative methods, Linear Algebra Appl. 267 (1997), 281 – 315. · Zbl 0891.65033
[6] 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. · Zbl 0922.65033 · doi:10.1023/A:1018974514896
[7] 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). · Zbl 1028.65018 · doi:10.1023/A:1012915424955
[8] 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. · Zbl 0990.65038 · doi:10.1023/A:1021913700691
[9] 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. · Zbl 1046.65018 · doi:10.1093/imanum/23.4.561
[10] Z.-Z. Bai and M.K. Ng, On inexact preconditioners for nonsymmetric matrices, SIAM J. Sci. Comput., 26(2005), 1710-1724. · Zbl 1077.65043
[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. · Zbl 1083.65045
[12] Zhongzhi Bai and Deren Wang, A class of new hybrid algebraic multilevel preconditioning methods, Linear Algebra Appl. 260 (1997), 223 – 255. · Zbl 0877.65023 · doi:10.1016/S0024-3795(97)80012-2
[13] 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. · Zbl 0995.49017
[14] Åke Björck, Numerical methods for least squares problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. · Zbl 0847.65023
[15] 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. · Zbl 0873.65031 · doi:10.1137/S0036142994273343
[16] Franco Brezzi and Michel Fortin, Mixed and hybrid finite element methods, Springer Series in Computational Mathematics, vol. 15, Springer-Verlag, New York, 1991. · Zbl 0788.73002
[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), no. 2, 181 – 204. · Zbl 0739.65018 · doi:10.1093/imanum/11.2.181
[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), no. 2, 227 – 257. · Zbl 0884.65020 · doi:10.1145/229473.229480
[19] Nira Dyn and Warren E. Ferguson Jr., The numerical solution of equality constrained quadratic programming problems, Math. Comp. 41 (1983), no. 163, 165 – 170. · Zbl 0527.49030
[20] 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. · Zbl 0524.65019 · doi:10.1137/0720023
[21] 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). · Zbl 1168.76348 · doi:10.1016/S0168-9274(02)00118-6
[22] 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. · Zbl 0815.65041 · doi:10.1137/0731085
[23] 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. · Zbl 1143.76531 · doi:10.1007/s002110100300
[24] B. Fischer, A. Ramage, D. J. Silvester, and A. J. Wathen, Minimum residual methods for augmented systems, BIT 38 (1998), no. 3, 527 – 543. · Zbl 0914.65026 · doi:10.1007/BF02510258
[25] Philip E. Gill, Walter Murray, and Margaret H. Wright, Practical optimization, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1981. · Zbl 0503.90062
[26] Roland Glowinski, Numerical methods for nonlinear variational problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984. · Zbl 0536.65054
[27] 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. · Zbl 0865.65009
[28] 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. · Zbl 0912.76053 · doi:10.1137/S106482759529382X
[29] Gene H. Golub, X. Wu, and Jin-Yun Yuan, SOR-like methods for augmented systems, BIT 41 (2001), no. 1, 71 – 85. · Zbl 0991.65036 · doi:10.1023/A:1021965717530
[30] 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. · Zbl 0999.65050 · doi:10.1137/S1064827598345667
[31] 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. · Zbl 0974.49021 · doi:10.1088/0266-5611/16/5/309
[32] Apostolos Hadjidimos, Accelerated overrelaxation method, Math. Comp. 32 (1978), no. 141, 149 – 157. · Zbl 0382.65015
[33] Jianming Jin, The finite element method in electromagnetics, 2nd ed., Wiley-Interscience [John Wiley & Sons], New York, 2002. · Zbl 1001.78001
[34] 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. · Zbl 0960.65052 · doi:10.1137/S0895479899351805
[35] 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). · Zbl 0917.73069 · doi:10.1137/S1064827596303624
[36] Peter A. Markowich, The stationary semiconductor device equations, Computational Microelectronics, Springer-Verlag, Vienna, 1986. · Zbl 0614.34013
[37] 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. · Zbl 0959.65063 · doi:10.1137/S1064827599355153
[38] 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). , https://doi.org/10.1002/1099-1506(200010/12)7:7/83.3.CO;2-6 · Zbl 1051.65038
[39] 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. · Zbl 0621.65059 · doi:10.1137/0607038
[40] Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. · Zbl 1031.65046
[41] 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. · Zbl 0599.65018 · doi:10.1137/0907058
[42] 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. · Zbl 0911.65131 · doi:10.1137/S1064827594275091
[43] S. Selberherr, Analysis and Simulation of Semiconductor Devices, Springer-Verlag, New York, 1984.
[44] Gilbert Strang, Introduction to applied mathematics, Wellesley-Cambridge Press, Wellesley, MA, 1986. · Zbl 0618.00015
[45] Walter Zulehner, Analysis of iterative methods for saddle point problems: a unified approach, Math. Comp. 71 (2002), no. 238, 479 – 505. · Zbl 0996.65038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.