A Note on Chebyshev Accelerated PMHSS Iteration Method for Block Two-by-Two Linear Systems

doi:10.1007/s42967-023-00300-x

Communications on Applied Mathematics and Computation ›› 2025, Vol. 7 ›› Issue (4): 1242-1263.doi: 10.1007/s42967-023-00300-x

• ORIGINAL PAPERS • 上一篇下一篇

A Note on Chebyshev Accelerated PMHSS Iteration Method for Block Two-by-Two Linear Systems

Zhao-Zheng Liang, Jun-Lin Tian, Hong-Yi Wan

School of Mathematics and Statistics, Lanzhou University, Lanzhou, 730000, Gansu, China

收稿日期:2022-12-30 修回日期:2023-06-05 接受日期:2023-07-18 出版日期:2023-09-20 发布日期:2023-09-20
通讯作者: Zhao-Zheng Liang,E-mail:liangzz@lzu.edu.cn E-mail:liangzz@lzu.edu.cn
作者简介:Jun-Lin Tian, E-mail:tianjl2019@lzu.edu.cn;Hong-Yi Wan, E-mail:wanhy19@lzu.edu.cn
基金资助:
This work is supported by the National Natural Science Foundation of China (Nos. 11801242, 11771193, and 11901267), the Fundamental Research Funds for the Central Universities (No. lzujbky-2022-05), and the Natural Science Foundation of Gansu Province of China (Grant No. 23JRRA1104).

A Note on Chebyshev Accelerated PMHSS Iteration Method for Block Two-by-Two Linear Systems

Zhao-Zheng Liang, Jun-Lin Tian, Hong-Yi Wan

School of Mathematics and Statistics, Lanzhou University, Lanzhou, 730000, Gansu, China

Received:2022-12-30 Revised:2023-06-05 Accepted:2023-07-18 Online:2023-09-20 Published:2023-09-20
Supported by:
This work is supported by the National Natural Science Foundation of China (Nos. 11801242, 11771193, and 11901267), the Fundamental Research Funds for the Central Universities (No. lzujbky-2022-05), and the Natural Science Foundation of Gansu Province of China (Grant No. 23JRRA1104).

摘要/Abstract

摘要： In this paper, the efficient preconditioned modified Hermitian and skew-Hermitian splitting (PMHSS) iteration method is further explored and it is extended to solve more general block two-by-two linear systems with different and nonsymmetric off-diagonal blocks. With the aid of the singular value decomposition technique, the detailed analysis of the algebraic and convergence properties of the PMHSS iteration method demonstrates that it is still convergent unconditionally as when it is used to solve the well-studied case of block two-by-two linear systems with same and symmetric off-diagonal blocks. Moreover, the PMHSS preconditioned matrix is almost unitary diagonalizable with clustered eigenvalue distributions for this more general case. On account of the favorable spectral properties of the PMHSS preconditioned matrix, a parameter free Chebyshev accelerated PMHSS (CAPMHSS) method is established to further improve its convergence rate. Numerical experiments about Kroncker structured block two-by-two linear systems arising from a time-dependent PDE-constrained optimal control problem demonstrate quite satisfactory and competitive performance of the CAPMHSS method compared with some existing preconditioned Krylov subspace methods.

关键词: Splitting iteration, Chebyshev acceleration, Convergence analysis, Block two-by-two linear system, PDE-constrained optimization

Abstract: In this paper, the efficient preconditioned modified Hermitian and skew-Hermitian splitting (PMHSS) iteration method is further explored and it is extended to solve more general block two-by-two linear systems with different and nonsymmetric off-diagonal blocks. With the aid of the singular value decomposition technique, the detailed analysis of the algebraic and convergence properties of the PMHSS iteration method demonstrates that it is still convergent unconditionally as when it is used to solve the well-studied case of block two-by-two linear systems with same and symmetric off-diagonal blocks. Moreover, the PMHSS preconditioned matrix is almost unitary diagonalizable with clustered eigenvalue distributions for this more general case. On account of the favorable spectral properties of the PMHSS preconditioned matrix, a parameter free Chebyshev accelerated PMHSS (CAPMHSS) method is established to further improve its convergence rate. Numerical experiments about Kroncker structured block two-by-two linear systems arising from a time-dependent PDE-constrained optimal control problem demonstrate quite satisfactory and competitive performance of the CAPMHSS method compared with some existing preconditioned Krylov subspace methods.

Key words: Splitting iteration, Chebyshev acceleration, Convergence analysis, Block two-by-two linear system, PDE-constrained optimization

中图分类号:

Zhao-Zheng Liang, Jun-Lin Tian, Hong-Yi Wan. A Note on Chebyshev Accelerated PMHSS Iteration Method for Block Two-by-Two Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1242-1263.

参考文献

[1] Amestoy, P.R., Davis, T.A., Duff, I.S.: An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17(4), 886-905 (1996)
[2] Amestoy, P.R., Davis, T.A., Duff, I.S.: Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Trans. Math. Software 30(3), 381-388 (2004)
[3] Arioli, M., Scott, J.: Chebyshev acceleration of iterative refinement. Numer. Algorithms 66(3), 591-608 (2014)
[4] Axelsson, O.: Iterative Solution Methods. Cambridge University Press, Cambridge (1994)
[5] Axelsson, O., Boyanova, P., Kronbichler, M., Neytcheva, M., Wu, X.: Numerical and computational efficiency of solvers for two-phase problems. Comput. Math. Appl. 65(3), 301-314 (2013)
[6] Axelsson, O., Farouq, S., Neytcheva, M.: Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems: Poisson and convection-diffusion control. Numer. Algorithms 73(3), 631-663 (2016)
[7] Axelsson, O., Farouq, S., Neytcheva, M.: Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems: Stokes control. Numer. Algorithms 74(1), 19-37 (2017)
[8] Axelsson, O., Neytcheva, M., Ahmad, B.: A comparison of iterative methods to solve complex valued linear algebraic systems. Numer. Algorithms 66(4), 811-841 (2014)
[9] Bai, Z.-Z.: Rotated block triangular preconditioning based on PMHSS. Sci. China Math. 56, 2523-2538 (2013)
[10] Bai, Z.-Z.: On preconditioned iteration methods for complex linear systems. J. Eng. Math. 93(1), 41-60 (2015)
[11] Bai, Z.-Z., Benzi, M., Chen, F.: Modified HSS iteration methods for a class of complex symmetric linear systems. Computing 87, 93-111 (2010)
[12] Bai, Z.-Z., Benzi, M., Chen, F.: On preconditioned MHSS iteration methods for complex symmetric linear systems. Numer. Algorithms 56(2), 297-317 (2011)
[13] Bai, Z.-Z., Benzi, M., Chen, F., Wang, Z.-Q.: Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems. IMA J. Numer. Anal. 33(1), 343-369 (2013)
[14] Bai, Z.-Z., Chen, F., Wang, Z.-Q.: Additive block diagonal preconditioning for block two-by-two linear systems of skew-Hamiltonian coefficient matrices. Numer. Algorithms 62(4), 655-675 (2013)
[15] 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(3), 603-626 (2003)
[16] 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), 1-32 (2004)
[17] Bai, Z.-Z., Hadjidimos, A.: Optimization of extrapolated Cayley transform with non-Hermitian positive definite matrix. Linear Algebra Appl. 310, 5-18 (2017)
[18] Bai, Z.-Z., Lu, K.-Y.: Optimal rotated block-diagonal preconditioning for discretized optimal control problems constrained with fractional time-dependent diffusive equations. Appl. Numer. Math. 163, 126-146 (2021)
[19] Bai, Z.-Z., Lu, K.-Y.: An economic implementation of the optimal rotated block-diagonal preconditioning method. Numer. Algorithms 93, 85-101 (2023)
[20] Bai, Z.-Z., Pan, J.-Y.: Matrix Analysis and Computations. SIAM, Philadelphia, PA (2021)
[21] Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1-137 (2005)
[22] Bosch, J., Stoll, M.: Preconditioning for vector-valued Cahn-Hilliard equations. SIAM J. Sci. Comput. 37(5), s216-s243 (2014)
[23] Elman, H.C., Ramage, A., Silvester, D.J.: IFISS: a computational laboratory for investigating incompressible flow problems. SIAM Rev. 56(2), 261-273 (2014)
[24] Golub, G.H., Overton, M.L.: The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems. Numer. Math. 53(5), 571-593 (1988)
[25] Golub, G.H., Varga, R.S.: Chebychev semi-iterative methods, successive over-relaxation iterative methods, and second-order Richardson iterative methods. Parts I and II. Numer. Math. 3(1), 147-168 (1961)
[26] Gutknecht, M., Röllin, S.: The Chebyshev iteration revisted. Parallel Comput. 28(2), 263-283 (2002)
[27] Hezari, D., Edalatpour, V., Salkuyeh, D.K.: Preconditioned GSOR iterative method for a class of complex symmetric system of linear equations. Numer. Linear Algebra Appl. 22(4), 761-776 (2015)
[28] Liang, Z.-Z., Zhang, G.-F.: Robust additive block triangular preconditioners for block two-by-two linear systems. Numer. Algorithms 82(2), 503-537 (2019)
[29] Liang, Z.-Z., Zhang, G.-F.: On Chebyshev accelerated iteration methods for two-by-two block linear systems. J. Comput. Appl. Math. 391, 113449 (2021)
[30] Manteuffel, T.A.: The Tchebychev iteration for nonsymmetric linear systems. Numer. Math. 28(3), 307-327 (1977)
[31] Ng, M.K., Pan, J.-Y.: Weighted Toeplitz regularized least squares computation for image restoration. SIAM J. Sci. Comput. 36(1), B94-B121 (2014)
[32] Nocedal, J., Wright, S. J.: Numerical optimization. In: Spinger Series in Operations Research, Springer-Verlag, New York (2006)
[33] Notay, Y.: AGMG software and documentation. http://agmg.eu/
[34] Orban, D., Arioli, M.: Iterative Solution of Symmetric Quasi-definite Linear Systems. SIAM, Philadelphia (2017)
[35] Pearson, J.W.: Preconditioned iterative methods for Navier-Stokes control problems. J. Comput. Phys. 292, 194-206 (2015)
[36] Pearson, J.W.: Fast iterative solvers for large matrix systems arising from time-dependent Stokes control problems. Appl. Numer. Math. 108, 87-101 (2016)
[37] Pearson, J.W., Stoll, M., Wathen, A.J.: Regularization-robust preconditioners for time-dependent PDE-constrained optimization problems. SIAM J. Matrix Anal. Appl. 33(4), 1126-1152 (2012)
[38] Pearson, J.W., Wathen, A.J.: Matching Schur complement approximations for certain saddle-point systems. In: Contemporary Computational Mathematics-A Celebration of the 80th Birthday of Ian Sloan, pp. 1001-1016. Springer (2018)
[39] Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia (2003)
[40] Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7(3), 856-869 (1986)
[41] Salkuyeh, D.K., Hezari, D., Edalatpour, V.: Generalized successive overrelaxation iterative method for a class of complex symmetric linear system of equations. Int. J. Comput. Math. 92(4), 802-815 (2015)
[42] Stoll, M., Wathen, A.J.: All-at-once solution of time-dependent PDE-constrained optimization problems. Technical Report 1017, The Mathematical Institute, University of Oxford (2010)
[43] Stoll, M., Wathen, A.J.: All-at-once solution of time-dependent Stokes control. J. Comput. Phy. 232(1), 498-515 (2013)
[44] Van Rienen, U.: Numerical Methods in Computational Electrodynamic: Linear Systems in Practical Applications. Springer, Berlin/Heidelberg (2001)
[45] Varga, R.S.: Matrix Iterative Analysis. Prentice Hall, Englewood Cliffs (1962)
[46] Wang, T., Lu, L.-Z.: Alternating-directional PMHSS iteration method for a class of two-by-two block linear systems. Appl. Math. Lett. 58, 159-164 (2016)
[47] Wang, Z.-Q.: On a Chebyshev accelerated splitting iteration method with application to two-by-two block linear systems. Numer. Linear Algebra Appl. 25(5), e2117 (2018)
[48] Wathen, A.J., Rees, T.: Chebyshev semi-iteration in preconditioning for problems including the mass matrix. Electron. Trans. Numer. Anal. 34, 125-135 (2009)

A Note on Chebyshev Accelerated PMHSS Iteration Method for Block Two-by-Two Linear Systems

A Note on Chebyshev Accelerated PMHSS Iteration Method for Block Two-by-Two Linear Systems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	Gang Bao, Peijun Li, Xiaokai Yuan. Convergence of the PML Method for the Biharmonic Wave Scattering Problem in Periodic Structures[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 1122-1145.
[2]	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.
[3]	Yuan Xu, Qiang Zhang. Superconvergence Analysis of the Runge-Kutta Discontinuous Galerkin Method with Upwind-Biased Numerical Flux for Two-Dimensional Linear Hyperbolic Equation[J]. Communications on Applied Mathematics and Computation, 2022, 4(1): 319-352.
[4]	Qingqing Wu, Zhongshu Wu, Xiaoyan Zeng. A Jacobi Spectral Collocation Method for Solving Fractional Integro-Differential Equations[J]. Communications on Applied Mathematics and Computation, 2021, 3(3): 509-526.
[5]	Somayeh Yeganeh, Reza Mokhtari, Jan S. Hesthaven. A Local Discontinuous Galerkin Method for Two-Dimensional Time Fractional Difusion Equations[J]. Communications on Applied Mathematics and Computation, 2020, 2(4): 689-709.