Construction and analysis of structured preconditioners for block two-by-two matrices
Tóm tắt
For the large sparse block two-by-two real nonsingular matrices, we establish a general framework of 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 high-quality preconditioning matrices for some typical matrices from the real-world applications.
Tài liệu tham khảo
Elman H C. Preconditurners for saddle point problems arising in computational fluid dynamics[J]. Appl. Nu-mer. Math., 2002, 43: 75–89.
Brezzi F, Fortin M. Mixed and Hybrid Finite Element Methods [M]. Springer-Verlag, New York, 1991.
Gill P E, Murray W, Wright M H. Practical Optimization [M]. Academic Press, New York, NY, 1981.
Keller C, Gould N I M, Wathen A J. Constrained preconditioning for indefinite linear systems [J]. SIAM J. Matrix Anal. Appl., 2001, 21: 1300–1317.
Markowich P A. The Stationary Semiconductor Device Equations [M]. Springer-Verlag, New York, NY, 1986.
Saad Y. Iterative Methods for Sparse Linear Systems [M]. 2nd Edition, SIAM, Philadelphia, PA, 2003.
Duff I S, Gould N I M, Reid J K, et al. The factorization of sparse symmetric indefinite matrices [J]. IMA J. Numer. Anal., 1991, 11: 181–204.
Duff I S, Reid J K. Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems [J]. ACM Trans. Math. Software, 1996, 22: 227–257.
Axelsson O. Iterative Solution Methods[M]. Cambridge University Press, Cambridge, 1994.
Bai Z Z. Parallel Iterative Methods for Large-Scale Systems of Algebraic Equations[D]. Doctoral Dissertation, Shanghai University of Science and Technology, Shanghai, June 1993.
Bramble J H, Pasciak J E, Vassilev A T. Analysis of the inexact Uzawa algorithm for saddle point problems[J]. SIAMJ. Numer. Anal., 1997, 34: 1072–1092.
Elman H C, Golub G H. Inexact and preconditioned Uzawa algorithms for saddle point problems[J]. SIAM J. Numer. Anal., 1994, 31:1645–1661.
Golub G H, Wathen A J. An iteration for indefinite systems and its application to the Navier-Stokes equations [J]. SIAMJ. Sci. Comput., 1998, 19: 530–539.
Golub G H, Wu X, Yuan J Y. SOR-like methods for augmented systems [J]. BIT, 2001, 41: 71–85.
Zulenher W. Analysis of iterative methods for saddle point problems: a unified approach [J]. Math. Corn-put., 2001, 71: 479–505.
Perugia I, Simoncini V. Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations [J]. Numer. Linear Algebra Appl., 2000, 7:585–616.
Klawonn A. Block-triangular preconditioners for saddle point problems with a penalty term[J]. SIAM J. Sci. Comput., 1998, 19: 172–184.
Murphy M F, Golub G H, Wathen A J. A note on preconditioning for indefinite linear systems [J]. SIAM J. Sci. Comput., 2000, 21: 1969–1972.
Bai Z Z. A class of modified block SSOR preconditioners for symmetric positive definite systems of linear equations [J]. Adv. Comput. Math., 1999, 10:169–186.
Bai Z Z. Modified block SSOR preconditioners for symmetric positive definite linear systems[J]. Ann. Operations Research, 2001, 103:263–282.
Bai Z Z, Li G Q. Restrictively preconditioned conjugate gradient methods for systems of linear equations [J]. IMA J. Numer. Anal., 2003, 23(4):561–580.
Bai Z Z, Duff I S, Wathen A J. A class of incomplete orthogonal factorization methods. I:methods and theories [J]. BIT, 2001, 41: 53–70.
Golub G H, Van Loan C F. Matrix Computations[M]. 3rd Edition, The Johns Hopkins University Press, Baltimore, London, 1996.
Saad Y, Schultz M H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems [J]. SIAMJ. Sci. Stat. Comput., 1986, 7: 856–869.
Hadjidimos A. Accelerated overrelaxation method[J]. Math. Comput., 1978, 32: 149–157.