×

Asymmetric Hermitian and skew-Hermitian splitting methods for positive definite linear systems. (English) Zbl 1127.65019

Stationary iterative methods for a linear system of equations \(Ax = b\) can be constructed by an additive splitting of the matrix \(A\). Z.-Z. Bai, G. H. Golub and M. K. Ng [SIAM J. Matrix Anal. Appl. 24, No. 3, 603–626 (2003; Zbl 1036.65032)] considered the splitting \(A = H + S\) with \(H = (A+A^*)/2\) and \(S = (A-A^*)/2\), leading to the so called HSS iteration \[ (\alpha I + H)x^{(k+1/2)}= (\alpha I - S) x^{(k)} + b, \quad (\alpha I + S) x^{(k+1)} = (\alpha I - H) x^{(k+1/2)} + b, \] where \(\alpha\) is a fixed positive parameter. This paper proposes to allow for a different parameter in the second part of this iteration: \[ (\alpha I + H)x^{(k+1/2)} = (\alpha I - S) x^{(k)} + b, \quad (\beta I + S) x^{(k+1)} = (\beta I - H) x^{(k+1/2)} + b, \] where \(\alpha\) is nonnegative and \(\beta\) is positive. Bounds on \(\beta\) are given for which this modified iteration converges to \(x\). A bound on the spectral radius of the iteration matrix is given, depending on \(\alpha,\beta\) and the eigenvalues of \(H,M\). Optimal values of the parameters for a simplified bound are computed. It turns out that, for an arbitrary \(\alpha\), the choice \(\beta = \alpha\) can be far from optimal. On the other hand, numerical experiments for the finite difference discretization of a \(3D\) convection-diffusion equation suggest that little improvement over the HSS iteration is made when \(\alpha\) is chosen optimally. Finally, existing results on the influence of the inexact solution of the subsystems (e.g., by Krylov subspace methods) on the convergence are extended.

MSC:

65F10 Iterative numerical methods for linear systems
65N06 Finite difference methods for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations

Citations:

Zbl 1036.65032
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856C869 (1986)
[2] Saad, Y.; Vorst, H. A.V. D., Iterative solution of linear systems in the 20th century, J. Comput. Appl. Math., 123, 1-33 (2000) · Zbl 0965.65051
[3] Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic Press: Academic Press New York · Zbl 0204.48102
[4] Benzi, M.; Golub, G. H., A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26, 20-41 (2004) · Zbl 1082.65034
[5] Bai, Z. Z.; Golub, G. H.; Ng, M. K., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24, 603-626 (2003) · Zbl 1036.65032
[6] Bai, Z. Z.; Golub, G. H.; Lu, L. Z.; Yin, J. F., Block triangular and skew-Hermitian splitting methods for positive-definite linear systems, SIAM J. Sci. Comput., 26, 844-863 (2005) · Zbl 1079.65028
[7] Z.Z. Bai, G.H. Golub, J.Y. Pan, Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Technical Report SCCM-02-12, Scientific Computing and Computational Mathematics Program, Department of Computer Science, Stanford University, Stanford, CA, 2002; Z.Z. Bai, G.H. Golub, J.Y. Pan, Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Technical Report SCCM-02-12, Scientific Computing and Computational Mathematics Program, Department of Computer Science, Stanford University, Stanford, CA, 2002 · Zbl 1056.65025
[8] Golub, G. H.; Vanderstraeten, D., On the preconditioning of matrices with a dominant skew-symmetric component, Numer. Algorithms, 25, 223-239 (2000) · Zbl 0983.65041
[9] Z.Z. Bai, G.H. Golub, M.K. Ng, On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iteration. Available online at: http://www.sccm.stanford.edu/wrap/pub-tech.html; Z.Z. Bai, G.H. Golub, M.K. Ng, On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iteration. Available online at: http://www.sccm.stanford.edu/wrap/pub-tech.html · Zbl 1199.65097
[10] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0865.65009
[11] Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS Publishing Company: PWS Publishing Company Boston · Zbl 1002.65042
[12] Chow, E.; Saad, Y., Experimental study of ILU preconditioners for indefinite matrices, J. Comput. Appl. Math., 86, 387-414 (1997) · Zbl 0891.65028
[13] Greif, C.; Varah, J., Iterative solution of cyclically reduced systems arising from discretization of the three-dimensional convection-diffusion equation, SIAM J. Sci. Comput., 19, 1918-1940 (1998) · Zbl 0916.65028
[14] Greif, C.; Varah, J., Block stationary methods for nonsymmetric cyclically reduced systems arising from discretization of the three-dimensional elliptic equation, SIAM J. Matrix Anal. Appl., 20, 1038-1059 (1999) · Zbl 0936.65125
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.