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

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.

Keywords

Splitting iteration / Chebyshev acceleration / Convergence analysis / Block two-by-two linear system / PDE-constrained optimization

References

[1] AmestoyPR, DavisTA, DuffIS. An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl., 1996, 174886-905

[2] AmestoyPR, DavisTA, DuffIS. Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Trans. Math. Software, 2004, 303381-388

[3] ArioliM, ScottJ. Chebyshev acceleration of iterative refinement. Numer. Algorithms, 2014, 663591-608

[4] AxelssonOIterative Solution Methods, 1994CambridgeCambridge University Press

[5] AxelssonO, BoyanovaP, KronbichlerM, NeytchevaM, WuX. Numerical and computational efficiency of solvers for two-phase problems. Comput. Math. Appl., 2013, 653301-314

[6] AxelssonO, FarouqS, NeytchevaM. Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems: Poisson and convection-diffusion control. Numer. Algorithms, 2016, 733631-663

[7] AxelssonO, FarouqS, NeytchevaM. Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems: Stokes control. Numer. Algorithms, 2017, 74119-37

[8] AxelssonO, NeytchevaM, AhmadB. A comparison of iterative methods to solve complex valued linear algebraic systems. Numer. Algorithms, 2014, 664811-841

[9] BaiZ-Z. Rotated block triangular preconditioning based on PMHSS. Sci. China Math., 2013, 56: 2523-2538

[10] BaiZ-Z. On preconditioned iteration methods for complex linear systems. J. Eng. Math., 2015, 93141-60

[11] BaiZ-Z, BenziM, ChenF. Modified HSS iteration methods for a class of complex symmetric linear systems. Computing, 2010, 87: 93-111

[12] BaiZ-Z, BenziM, ChenF. On preconditioned MHSS iteration methods for complex symmetric linear systems. Numer. Algorithms, 2011, 562297-317

[13] BaiZ-Z, BenziM, ChenF, WangZ-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., 2013, 331343-369

[14] BaiZ-Z, ChenF, WangZ-Q. Additive block diagonal preconditioning for block two-by-two linear systems of skew-Hamiltonian coefficient matrices. Numer. Algorithms, 2013, 624655-675

[15] BaiZ-Z, GolubGH, NgMK. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl., 2003, 243603-626

[16] BaiZ-Z, GolubGH, PanJ-Y. Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems. Numer. Math., 2004, 9811-32

[17] BaiZ-Z, HadjidimosA. Optimization of extrapolated Cayley transform with non-Hermitian positive definite matrix. Linear Algebra Appl., 2017, 310: 5-18

[18] BaiZ-Z, LuK-Y. Optimal rotated block-diagonal preconditioning for discretized optimal control problems constrained with fractional time-dependent diffusive equations. Appl. Numer. Math., 2021, 163: 126-146

[19] BaiZ-Z, LuK-Y. An economic implementation of the optimal rotated block-diagonal preconditioning method. Numer. Algorithms, 2023, 93: 85-101

[20] BaiZ-Z, PanJ-YMatrix Analysis and Computations, 2021Philadelphia, PASIAM

[21] BenziM, GolubGH, LiesenJ. Numerical solution of saddle point problems. Acta Numer., 2005, 14: 1-137

[22] BoschJ, StollM. Preconditioning for vector-valued Cahn-Hilliard equations. SIAM J. Sci. Comput., 2014, 375s216-s243

[23] ElmanHC, RamageA, SilvesterDJ. IFISS: a computational laboratory for investigating incompressible flow problems. SIAM Rev., 2014, 562261-273

[24] GolubGH, OvertonML. The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems. Numer. Math., 1988, 535571-593

[25] GolubGH, VargaRS. Chebychev semi-iterative methods, successive over-relaxation iterative methods, and second-order Richardson iterative methods. Parts I and II. Numer. Math., 1961, 31147-168

[26] GutknechtM, RöllinS. The Chebyshev iteration revisted. Parallel Comput., 2002, 282263-283

[27] HezariD, EdalatpourV, SalkuyehDK. Preconditioned GSOR iterative method for a class of complex symmetric system of linear equations. Numer. Linear Algebra Appl., 2015, 224761-776

[28] LiangZ-Z, ZhangG-F. Robust additive block triangular preconditioners for block two-by-two linear systems. Numer. Algorithms, 2019, 822503-537

[29] LiangZ-Z, ZhangG-F. On Chebyshev accelerated iteration methods for two-by-two block linear systems. J. Comput. Appl. Math., 2021, 391113449

[30] ManteuffelTA. The Tchebychev iteration for nonsymmetric linear systems. Numer. Math., 1977, 283307-327

[31] NgMK, PanJ-Y. Weighted Toeplitz regularized least squares computation for image restoration. SIAM J. Sci. Comput., 2014, 361B94-B121

[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] OrbanD, ArioliMIterative Solution of Symmetric Quasi-definite Linear Systems, 2017PhiladelphiaSIAM

[35] PearsonJW. Preconditioned iterative methods for Navier-Stokes control problems. J. Comput. Phys., 2015, 292: 194-206

[36] PearsonJW. Fast iterative solvers for large matrix systems arising from time-dependent Stokes control problems. Appl. Numer. Math., 2016, 108: 87-101

[37] PearsonJW, StollM, WathenAJ. Regularization-robust preconditioners for time-dependent PDE-constrained optimization problems. SIAM J. Matrix Anal. Appl., 2012, 3341126-1152

[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] SaadY, SchultzMH. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., 1986, 73856-869

[41] SalkuyehDK, HezariD, EdalatpourV. Generalized successive overrelaxation iterative method for a class of complex symmetric linear system of equations. Int. J. Comput. Math., 2015, 924802-815

[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] StollM, WathenAJ. All-at-once solution of time-dependent Stokes control. J. Comput. Phy., 2013, 2321498-515

[44] Van RienenUNumerical Methods in Computational Electrodynamic: Linear Systems in Practical Applications, 2001Springer

[45] VargaRSMatrix Iterative Analysis, 1962Englewood CliffsPrentice Hall

[46] WangT, LuL-Z. Alternating-directional PMHSS iteration method for a class of two-by-two block linear systems. Appl. Math. Lett., 2016, 58: 159-164

[47] WangZ-Q. On a Chebyshev accelerated splitting iteration method with application to two-by-two block linear systems. Numer. Linear Algebra Appl., 2018, 255e2117

[48] WathenAJ, ReesT. Chebyshev semi-iteration in preconditioning for problems including the mass matrix. Electron. Trans. Numer. Anal., 2009, 34: 125-135

Funding

National Natural Science Foundation of China(11801242)

Fundamental Research Funds for the Central Universities(lzujbky-2022-05)

RIGHTS & PERMISSIONS

Shanghai University