Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices
Authors:
Zhong-Zhi Bai, Gene H. Golub and Chi-Kwong Li
Journal:
Math. Comp. 76 (2007), 287-298
MSC (2000):
Primary 65F10, 65F50
DOI:
https://doi.org/10.1090/S0025-5718-06-01892-8
Published electronically:
August 31, 2006
MathSciNet review:
2261022
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
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.
- 1. 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, https://doi.org/10.1016/S0024-3795(98)10093-9
- 2. 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.
- 3. 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, https://doi.org/10.1137/S0895479801395458
- 4. 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, https://doi.org/10.1007/s00211-004-0521-1
- 5. 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, https://doi.org/10.1016/0096-3003(95)00297-9
- 6. 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, https://doi.org/10.1093/imanum/23.4.561
- 7. 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, https://doi.org/10.1016/S0168-9274(98)00062-2
- 8. 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, https://doi.org/10.1137/040604091
- 9. 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.
- 10. 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, https://doi.org/10.1016/j.cam.2005.03.044
- 11. 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, https://doi.org/10.1137/S0895479802417106
- 12. 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, https://doi.org/10.1007/s00211-004-0574-1
- 13. 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
- 14. 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, https://doi.org/10.1137/0720023
- 15. 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, https://doi.org/10.1137/0723004
- 16. 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, https://doi.org/10.1007/s002110100300
- 17. 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
- 18. 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, https://doi.org/10.1137/S1064827500375096
- 19. 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, https://doi.org/10.1023/A:1016030016985
- 20. 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, https://doi.org/10.1023/A:1016637813615
- 21. 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
- 22. 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, https://doi.org/10.1137/S106482759529382X
- 23. 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, https://doi.org/10.1002/(SICI)1097-0207(19961130)39:22<3809::AID-NME26>3.0.CO;2-2
- 24. 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.
- 25. 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, https://doi.org/10.1137/S1064827599355153
- 26. 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, https://doi.org/10.1016/S0024-3795(01)00275-0
- 27. 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, https://doi.org/10.1137/0730031
- 28. Shmuel L. Weissman, High-accuracy low-order three-dimensional brick elements, Internat. J. Numer. Methods Engrg. 39 (1996), no. 14, 2337–2361. MR 1399024, https://doi.org/10.1002/(SICI)1097-0207(19960730)39:14<2337::AID-NME957>3.0.CO;2-7
- 29. 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, https://doi.org/10.1023/B:BITN.0000025084.86306.0a
Retrieve articles in Mathematics of Computation with MSC (2000): 65F10, 65F50
Retrieve articles in all journals with MSC (2000): 65F10, 65F50
Additional Information
Zhong-Zhi Bai
Affiliation:
Department of Mathematics, Fudan University, Shanghai 200433, People’s Republic of China, and State Key Laboratory of Scientific/Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, P.O. Box 2719, Beijing 100080, People’s Republic of China
Email:
bzz@lsec.cc.ac.cn
Gene H. Golub
Affiliation:
Scientific Computing and Computational Mathematics Program, Department of Computer Science, Stanford University, Stanford, California 94305-9025
Email:
golub@sccm.stanford.edu
Chi-Kwong Li
Affiliation:
Department of Mathematics, The College of William & Mary, P.O. Box 8795, Williamsburg, Virginia 23187-8795
Email:
ckli@math.wm.edu
DOI:
https://doi.org/10.1090/S0025-5718-06-01892-8
Keywords:
Non-Hermitian matrix,
positive semidefinite matrix,
Hermitian and skew-Hermitian splitting,
splitting iteration method,
convergence.
Received by editor(s):
February 11, 2005
Published electronically:
August 31, 2006
Additional Notes:
The work of the first author was supported by The Special Funds For Major State Basic Research Projects (No. G1999032803), The National Basic Research Program (No. 2005CB321702), The China NNSF Outstanding Young Scientist Foundation (No. 10525102) and The National Natural Science Foundation (No. 10471146), P.R. China, and The 2004 Ky and Yu-Fen Fan Fund Travel Grant of American Mathematical Society
The work of the second author was in part supported by the Department of Energy: DE-FC02-01ER41177
The research of the third author was partially supported by an NSF grant.
Article copyright:
© Copyright 2006
American Mathematical Society