Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices

Bai, Zhong-Zhi; Golub, Gene; Li, Chi-Kwong

doi:10.1090/S0025-5718-06-01892-8

Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices
HTML articles powered by AMS MathViewer

by Zhong-Zhi Bai, Gene H. Golub and Chi-Kwong Li PDF

Math. Comp. 76 (2007), 287-298 Request permission

Abstract:

For the non-Hermitian and positive semidefinite systems of linear equations, we derive necessary and sufficient conditions for guaranteeing the unconditional convergence of the preconditioned Hermitian and skew-Hermitian splitting iteration methods. We then apply these results to block tridiagonal linear systems in order to obtain convergence conditions for the corresponding block variants of the preconditioned Hermitian and skew-Hermitian splitting iteration methods.

References

Zhong-Zhi Bai, A class of parallel decomposition-type relaxation methods for large sparse systems of linear equations, Linear Algebra Appl. 282 (1998), no. 1-3, 1–24. MR 1648288, DOI 10.1016/S0024-3795(98)10093-9
Z.-Z. Bai and G.H. Golub, Generalized preconditioned Hermitian and skew-Hermitian splitting methods for saddle-point problems, Technical Report SCCM-04-07, Scientific Computing and Computational Mathematics Program, Department of Computer Science, Stanford University, 2004.
Zhong-Zhi Bai, Gene H. Golub, and Michael K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl. 24 (2003), no. 3, 603–626. MR 1972670, DOI 10.1137/S0895479801395458
Zhong-Zhi Bai, Gene H. Golub, and Jian-Yu Pan, Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Numer. Math. 98 (2004), no. 1, 1–32. MR 2076052, DOI 10.1007/s00211-004-0521-1
Zhongzhi Bai and Yangfeng Su, On the convergence of a class of parallel decomposition-type relaxation methods, Appl. Math. Comput. 81 (1997), no. 1, 1–21. MR 1417759, DOI 10.1016/0096-3003(95)00297-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. MR 2011340, DOI 10.1093/imanum/23.4.561
Zhong-Zhi Bai and Reinhard Nabben, Some properties of the block matrices in the parallel decomposition-type relaxation methods, Appl. Numer. Math. 29 (1999), no. 2, 167–170. MR 1666521, DOI 10.1016/S0168-9274(98)00062-2
Zhong-Zhi Bai and Michael K. Ng, On inexact preconditioners for nonsymmetric matrices, SIAM J. Sci. Comput. 26 (2005), no. 5, 1710–1724. MR 2142592, DOI 10.1137/040604091
Z.-Z. Bai, B.N. Parlett and Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102:1(2005), 1-38.
Zhong-Zhi Bai and Zeng-Qi Wang, Restrictive preconditioners for conjugate gradient methods for symmetric positive definite linear systems, J. Comput. Appl. Math. 187 (2006), no. 2, 202–226. MR 2185669, DOI 10.1016/j.cam.2005.03.044
Michele Benzi and Gene H. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl. 26 (2004), no. 1, 20–41. MR 2112850, DOI 10.1137/S0895479802417106
Daniele Bertaccini, Gene H. Golub, Stefano Serra Capizzano, and Cristina Tablino Possio, Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation, Numer. Math. 99 (2005), no. 3, 441–484. MR 2117735, DOI 10.1007/s00211-004-0574-1
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
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 and Martin H. Schultz, Preconditioning by fast direct methods for nonselfadjoint nonseparable elliptic equations, SIAM J. Numer. Anal. 23 (1986), no. 1, 44–57. MR 821905, DOI 10.1137/0723004
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
Michel Fortin and Roland Glowinski, Augmented Lagrangian methods, Studies in Mathematics and its Applications, vol. 15, North-Holland Publishing Co., Amsterdam, 1983. Applications to the numerical solution of boundary value problems; Translated from the French by B. Hunt and D. C. Spicer. MR 724072
Gene H. Golub and Chen Greif, On solving block-structured indefinite linear systems, SIAM J. Sci. Comput. 24 (2003), no. 6, 2076–2092. MR 2005622, DOI 10.1137/S1064827500375096
Gene H. Golub, Chen Greif, and James M. Varah, Block orderings for tensor-product grids in two and three dimensions, Numer. Algorithms 30 (2002), no. 2, 93–111. MR 1917293, DOI 10.1023/A:1016030016985
Gene H. Golub and Denis Vanderstraeten, On the preconditioning of matrices with skew-symmetric splittings, Numer. Algorithms 25 (2000), no. 1-4, 223–239. Mathematical journey through analysis, matrix theory and scientific computation (Kent, OH, 1999). MR 1827156, DOI 10.1023/A:1016637813615
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
Hormoz Modaressi and Philippe Aubert, A diffuse element-finite element technique for transient coupled analysis, Internat. J. Numer. Methods Engrg. 39 (1996), no. 22, 3809–3838. MR 1417791, DOI 10.1002/(SICI)1097-0207(19961130)39:22<3809::AID-NME26>3.0.CO;2-2
J.J. Modi, Parallel Algorithms and Matrix Computation, In Oxford Applied Mathematics and Computing Science Series, J.N. Buxton, R.F. Churchhouse and A.B. Tayler eds., Clarendon Press, Oxford, 1988.
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
Chuan-Long Wang and Zhong-Zhi Bai, Sufficient conditions for the convergent splittings of non-Hermitian positive definite matrices, Linear Algebra Appl. 330 (2001), no. 1-3, 215–218. MR 1826657, DOI 10.1016/S0024-3795(01)00275-0
Andrew Wathen and David Silvester, Fast iterative solution of stabilised Stokes systems. I. Using simple diagonal preconditioners, SIAM J. Numer. Anal. 30 (1993), no. 3, 630–649. MR 1220644, DOI 10.1137/0730031
Shmuel L. Weissman, High-accuracy low-order three-dimensional brick elements, Internat. J. Numer. Methods Engrg. 39 (1996), no. 14, 2337–2361. MR 1399024, DOI 10.1002/(SICI)1097-0207(19960730)39:14<2337::AID-NME957>3.0.CO;2-7
Jinxi Zhao, Weiguo Wang, and Weiqing Ren, Stability of the matrix factorization for solving block tridiagonal symmetric indefinite linear systems, BIT 44 (2004), no. 1, 181–188. MR 2057369, DOI 10.1023/B:BITN.0000025084.86306.0a