Semi-regularized Hermitian and Skew-Hermitian Splitting Preconditioning for Saddle-Point Linear Systems

doi:10.1007/s42967-022-00208-y

摘要/Abstract

摘要： In this paper, a two-step semi-regularized Hermitian and skew-Hermitian splitting (SHSS) iteration method is constructed by introducing a regularization matrix in the (1,1)-block of the first iteration step, to solve the saddle-point linear system. By carefully selecting two different regularization matrices, two kinds of SHSS preconditioners are proposed to accelerate the convergence rates of the Krylov subspace iteration methods. Theoretical analysis about the eigenvalue distribution demonstrates that the proposed SHSS preconditioners can make the eigenvalues of the corresponding preconditioned matrices be clustered around 1 and uniformly bounded away from 0. The eigenvector distribution and the upper bound on the degree of the minimal polynomial of the SHSS-preconditioned matrices indicate that the SHSS-preconditioned Krylov subspace iterative methods can converge to the true solution within finite steps in exact arithmetic. In addition, the numerical example derived from the optimal control problem shows that the SHSS preconditioners can significantly improve the convergence speeds of the Krylov subspace iteration methods, and their convergence rates are independent of the discrete mesh size.

关键词: Hermitian and skew-Hermitian splitting(HSS), Eigenvalues, Eigenvectors, Preconditioner, Saddle-point linear system

Abstract: In this paper, a two-step semi-regularized Hermitian and skew-Hermitian splitting (SHSS) iteration method is constructed by introducing a regularization matrix in the (1,1)-block of the first iteration step, to solve the saddle-point linear system. By carefully selecting two different regularization matrices, two kinds of SHSS preconditioners are proposed to accelerate the convergence rates of the Krylov subspace iteration methods. Theoretical analysis about the eigenvalue distribution demonstrates that the proposed SHSS preconditioners can make the eigenvalues of the corresponding preconditioned matrices be clustered around 1 and uniformly bounded away from 0. The eigenvector distribution and the upper bound on the degree of the minimal polynomial of the SHSS-preconditioned matrices indicate that the SHSS-preconditioned Krylov subspace iterative methods can converge to the true solution within finite steps in exact arithmetic. In addition, the numerical example derived from the optimal control problem shows that the SHSS preconditioners can significantly improve the convergence speeds of the Krylov subspace iteration methods, and their convergence rates are independent of the discrete mesh size.

Key words: Hermitian and skew-Hermitian splitting(HSS), Eigenvalues, Eigenvectors, Preconditioner, Saddle-point linear system

中图分类号:

Kang-Ya Lu, Shu-Jiao Li. Semi-regularized Hermitian and Skew-Hermitian Splitting Preconditioning for Saddle-Point Linear Systems[J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1422-1445.

参考文献

1. Axelsson, O., Neytcheva, M.: Preconditioning methods for linear systems arising in constrained optimization problems. Numer. Linear Algebra Appl. 10, 3-31 (2003)
2. Bai, Z.-Z.: Structured preconditioners for nonsingular matrices of block two-by-two structures. Math. Comput. 75, 791-815 (2006)
3. Bai, Z.-Z.: Regularized HSS iteration methods for stabilized saddle-point problems. IMA J. Numer. Anal. 39, 1888-1923 (2019)
4. Bai, Z.-Z., Benzi, M.: Regularized HSS iteration methods for saddle-point linear systems. BIT Numer. Math. 57, 287-311 (2017)
5. Bai, Z.-Z., Golub, G.H.: Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems. IMA J. Numer. Anal. 27, 1-23 (2007)
6. Bai, Z.-Z., Golub, G.H., Li, C.-K.: Optimal parameter in Hermitian and skew-Hermitian splitting method for certain two-by-two block matrices. SIAM J. Sci. Comput. 28, 583-603 (2006)
7. 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)
8. Bai, Z.-Z., Golub, G.H., Pan, J.-Y.: Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems. Numer. Math. 98, 1-32 (2004)
9. Bai, Z.-Z., Ng, M.K.: On inexact preconditioners for nonsymmetric matrices. SIAM J. Sci. Comput. 26, 1710-1724 (2005)
10. Bai, Z.-Z., Ng, M.K., Wang, Z.-Q.: Constraint preconditioners for symmetric indefinite matrices. SIAM J. Matrix Anal. Appl. 31, 410-433 (2009)
11. Bai, Z.-Z., Pan, J.-Y.: Matrix Analysis and Computations. SIAM, Philadelphia (2021)
12. Bai, Z.-Z., Parlett, B.N., Wang, Z.-Q.: On generalized successive overrelaxation methods for augmented linear systems. Numer. Math. 102, 1-38 (2005)
13. Bai, Z.-Z., Wang, Z.-Q.: On parameterized inexact Uzawa methods for generalized saddle point problems. Linear Algebra Appl. 428, 2900-2932 (2008)
14. Behzadi, R., Abdollahi, F.: Accelerated RHSS iteration methods for saddle-point linear systems. U.P.B. Sci. Bull. Ser. A 80, 153-162 (2018)
15. Benzi, M., Golub, G.H.: A preconditioner for generalized saddle point problems. SIAM J. Matrix Anal. Appl. 26, 20-41 (2004)
16. Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1-137 (2005)
17. Cao, Y.: Regularized DPSS preconditioners for non-Hermitian saddle point problems. Appl. Math. Lett. 84, 96-102 (2018)
18. Cao, Y., Chen, Y.-T.: Eigenvalue estimates of the regularized HSS preconditioned saddle point matrix. Math. Numer. Sin. 42, 51-62 (2020)
19. Cao, Y., Shi, Z.-Q., Shi, Q.: Regularized DPSS preconditioners for generalized saddle point linear systems. Comput. Math. Appl. 80, 956-972 (2020)
20. Cao, Y., Yao, L.-Q., Jiang, M.-Q., Niu, Q.: A relaxed HSS preconditioner for saddle point problems from meshfree discretization. J. Comput. Math. 31, 398-421 (2013)
21. Dollar, H.S., Wathen, A.J.: Approximate factorization constraint preconditioners for saddle point matrices. SIAM J. Sci. Comput. 27, 1555-1572 (2006)
22. Golub, G.H., Wu, X., Yuan, J.-Y.: SOR-like methods for augmented systems. BIT Numer. Math. 41, 71-85 (2001)
23. Hu, Q.-Y., Zou, J.: An iterative method with variable relaxation parameters for saddle-point problems. SIAM J. Matrix Anal. Appl. 23, 317-338 (2001)
24. Keller, C., Gould, N.I.M., Wathen, A.J.: Constraint preconditioning for indefinite linear systems. SIAM J. Matrix Anal. Appl. 21, 1300-1317 (2000)
25. Klawonn, A.: Block-triangular preconditioners for saddle-point problems with a penalty term. SIAM J. Sci. Comput. 19, 172-184 (1998)
26. Pan, J.-Y., Ng, M.K., Bai, Z.-Z.: New preconditioners for saddle point problems. Appl. Math. Comput. 172, 762-771 (2006)
27. Pearson, J.W., Stoll, M., Wathen, A.J.: Preconditioners for state-constrained optimal control problems with Moreau-Yosida penalty function. Numer. Linear Algebra Appl. 21, 81-97 (2014)
28. Perugia, I., Simoncini, V.: Block-diagonal and indefinite symmetric preconditioners for mixed element formulations. Numer. Linear Algebra Appl. 7, 585-616 (2000)
29. Powell, C.E., Silvester, D.: Optimal preconditioning for Raviart-Thomas mixed formulation of secondorder elliptic problems. SIAM J. Matrix Anal. Appl. 25, 718-738 (2004)
30. Rees, T., Stoll, M.: Block-triangular preconditioners for PDE-constrained optimization. Numer. Linear Algebra Appl. 17, 977-996 (2010)
31. Rozložník, M., Simoncini, V.: Krylov subspace methods for saddle point problems with indefinite preconditioning. SIAM J. Matrix Anal. Appl. 24, 368-391 (2002)
32. Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)
33. Shen, Q.-Q., Cao, Y., Wang, L.: Two improvements of the deteriorated PSS preconditioner for generalized saddle point problems. Numer. Algorithm 75, 33-54 (2017)
34. Simoncini, V.: Block triangular preconditioners for symmetric saddle-point problems. Appl. Numer. Math. 49, 63-80 (2004)
35. Strikwerda, J.C.: An iterative method for solving finite difference approximations to the Stokes equations. SIAM J. Numer. Anal. 21, 447-458 (1984)
36. Yang, A.-L.: Scaled norm minimization method for computing the parameters of the HSS and the twoparameter HSS preconditioners. Numer. Linear Algebra Appl. 25, e2169 (2018)
37. Zhang, J.-L.: On the regularization matrix of the regularized DPSS preconditioner for non-Hermitian saddle-point problems. Comput. Appl. Math. 39, 191 (2020)

[1]	Bo Wu, Xingbao Gao. Two-Parameter Block Triangular Splitting Preconditioner for Block Two-by-Two Linear Systems[J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1601-1615.
[2]	Will Pazner, Tzanio Kolev. Uniform Subspace Correction Preconditioners for Discontinuous Galerkin Methods with hp-Refnement[J]. Communications on Applied Mathematics and Computation, 2022, 4(2): 697-727.
[3]	Ju, Li Zhang. On the Preconditioning Properties of RHSS Preconditioner for Saddle-Point Linear Systems[J]. Communications on Applied Mathematics and Computation, 2021, 3(1): 177-187.
[4]	Xue-lei Lin, Pin Lyu, Michael K. Ng, Hai-Wei Sun, Seakweng Vong. An Efcient Second-Order Convergent Scheme for One-Side Space Fractional Difusion Equations with Variable Coefcients[J]. Communications on Applied Mathematics and Computation, 2020, 2(2): 215-239.
[5]	Jianguo Huang, Xuehai Huang. A Two-Level Additive Schwarz Preconditioner for Local C⁰ Discontinuous Galerkin Methods of Kirchhof Plates[J]. Communications on Applied Mathematics and Computation, 2019, 1(2): 167-185.
[6]	Hui Xie, Xuejun Xu. Domain Decomposition Preconditioners for Mixed Finite-Element Discretization of High-Contrast Elliptic Problems[J]. Communications on Applied Mathematics and Computation, 2019, 1(1): 141-165.