Abstract
For the singular, non-Hermitian, and positive semidefinite systems of linear equations, we derive necessary and sufficient conditions for guaranteeing the semi-convergence of the Hermitian and skew-Hermitian splitting (HSS) iteration methods. We then investigate the semi-convergence factor and estimate its upper bound for the HSS iteration method. If the semi-convergence condition is satisfied, it is shown that the semi-convergence rate is the same as that of the HSS iteration method applied to a linear system with the coefficient matrix equal to the compression of the original matrix on the range space of its Hermitian part, that is, the matrix obtained from the original matrix by restricting the domain and projecting the range space to the range space of the Hermitian part. In particular, an upper bound is obtained in terms of the largest and the smallest nonzero eigenvalues of the Hermitian part of the coefficient matrix. In addition, applications of the HSS iteration method as a preconditioner for Krylov subspace methods such as GMRES are investigated in detail, and several examples are used to illustrate the theoretical results and examine the numerical effectiveness of the HSS iteration method served either as a preconditioner for GMRES or as a solver.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bai Z-Z (2007) Splitting iteration methods for non-Hermitian positive definite systems of linear equations. Hokkaido Math J 36: 801–814
Bai Z-Z, Golub GH (2002) Generalized preconditioned Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems. Tech. Report SCCM-04-07, Scientific Computing and Computational Mathematics Program, Department of Computer Science, Stanford University. Available on line at http://www-sccm.stanford.edu/
Bai Z-Z, Golub GH (2007) Accelerated Hermitian and skew-Hermitian splitting methods for saddle-point problems. IMA J Numer Anal 27: 1–23
Bai Z-Z, Golub GH, Li C-K (2006) Optimal parameter in Hermitian and skew-Hermitian splitting method for certain two-by-two block matrices. SIAM J Sci Comput 28: 583–603
Bai Z-Z, Golub GH, Li C-K (2007) Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices. Math Comput 76: 287–298
Bai Z-Z, Golub GH, Lu L-Z, Yin J-F (2005) Block triangular and skew-Hermitian splitting methods for positive-definite linear systems. SIAM J Sci Comput 26: 844–863
Bai Z-Z, Golub GH, Ng MK (2003) Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J Matrix Anal Appl 24: 603–626
Bai Z-Z, Golub GH, Ng MK (2002) On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations. Tech. Report SCCM-02-06, Scientific Computing and Computational Mathematics Program, Department of Computer Science, Stanford University. Available on line at http://www-sccm.stanford.edu/
Bai Z-Z, Golub GH, Ng MK (2007) On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations. Numer Linear Algebra Appl 14: 319–335
Bai Z-Z, Golub GH, Pan J-Y (2004) Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems. Numer Math 98: 1–32
Bai Z-Z, Wang L, Yuan J-Y (2003) Weak convergence theory of quasi-nonnegative splittings for singular matrices. Appl Numer Math 47: 75–89
Benzi M, Golub GH (2004) A preconditioner for generalized saddle point problems. SIAM J Matrix Anal Appl 26: 20–41
Berman A, Plemmons RJ (1994) Nonnegative matrices in the mathematical sciences, 2nd edn. SIAM, Philadelphia
Bertaccini D, Golub GH, Serra Capizzano S, Tablino Possio C (2005) Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation. Numer Math 99: 441–484
Elman HC, Schultz MH (1986) Preconditioning by fast direct methods for nonself-adjoint nonseparable elliptic equations. SIAM J Numer Anal 23: 44–57
Elman HC, Silvester DJ, Wathen AJ (2002) Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations. Numer Math 90: 665–688
Golub GH, Greif C (2003) On solving block-structured indefinite linear systems. SIAM J Sci Comput 24: 2076–2092
Golub GH, Van Loan CF (1996) Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore and London
Golub GH, Wathen AJ (1998) An iteration for indefinite systems and its application to the Navier-Stokes equations. SIAM J Sci Comput 19: 530–539
Ortega JM, Rheinboldt WC (1970) Iterative solution of nonlinear equations in several variables. Academic Press, New York
Pan J-Y, Ng MK, Bai Z-Z (2006) New preconditioners for saddle point problems. Appl Math Comput 172: 762–771
Li W, Sun W-W (2000) Modified Gauss-Seidel type methods and Jacobi type methods for Z-matrix. Linear Algebra Appl 317: 227–240
Saad Y (2003) Iterative methods for sparse linear systems, 2nd edn. SIAM, Philadelphia
Song Y-Z (2000) Semiconvergence of nonnegative splittings for singular matrices. Numer Math 85: 109–127
Wathen AJ, Silvester DJ (1993) Fast iterative solution of stabilized Stokes systems. Part I: using simple diagonal preconditioners. SIAM J Numer Anal 30: 630–649
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by C.C. Douglas.
Supported by The National Basic Research Program (No. 2005CB321702), The China Outstanding Young Scientist Foundation (No. 10525102) and The National Natural Science Foundation (No. 10471146), People’s Republic of China.
Rights and permissions
About this article
Cite this article
Bai, ZZ. On semi-convergence of Hermitian and skew-Hermitian splitting methods for singular linear systems. Computing 89, 171–197 (2010). https://doi.org/10.1007/s00607-010-0101-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00607-010-0101-4
Keywords
- Singular linear system
- Non-Hermitian matrix
- Positive semidefinite matrix
- Hermitian and skew-Hermitian splitting
- Splitting iteration method
- Semi-convergence
- Preconditioning matrix
- Krylov subspace method