×

A sine transform based preconditioned MINRES method for all-at-once systems from constant and variable-coefficient evolutionary PDEs. (English) Zbl 1535.65040

Summary: In this work, we propose a simple yet generic preconditioned Krylov subspace method for a large class of nonsymmetric block Toeplitz all-at-once systems arising from discretizing evolutionary partial differential equations. Namely, our main result is to propose two novel symmetric positive definite preconditioners, which can be efficiently diagonalized by the discrete sine transform matrix. More specifically, our approach is to first permute the original linear system to obtain a symmetric one and subsequently develop desired preconditioners based on the spectral symbol of the modified matrix. Then, we show that the eigenvalues of the preconditioned matrix sequences are clustered around \(\pm 1\), which entails rapid convergence when the minimal residual method is devised. Alternatively, when the conjugate gradient method on the normal equations is used, we show that our preconditioner is effective in the sense that the eigenvalues of the preconditioned matrix sequence are clustered around unity. An extension of our proposed preconditioned method is given for high-order backward difference time discretization schemes, which can be applied on a wide range of time-dependent equations. Numerical examples are given, also in the variable-coefficient setting, to demonstrate the effectiveness of our proposed preconditioners, which consistently outperforms an existing block circulant preconditioner discussed in the relevant literature.

MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
15B05 Toeplitz, Cauchy, and related matrices
65M22 Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs

Software:

MGRIT; PARALAAOMPI

References:

[1] Barakitis, N., Ekstrom, S.E., Vassalos, P.: Preconditioners for fractional diffusion equations based on the spectral symbol. Numerical Linear Algebra with Applications, e2441 (2022). doi:10.1002/nla.2441 · Zbl 07584149
[2] Barbarino, G.: A systematic approach to reduced GLT. BIT Numer. Math. 1-63 (2021). doi:10.1007/s10543-021-00896-7
[3] Benzi, M.; Golub, GH, Bounds for the entries of matrix functions with applications to preconditioning, BIT Numer. Math., 39, 3, 417-438, 1999 · Zbl 0934.65054 · doi:10.1023/A:1022362401426
[4] Bertaccini, D.: Reliable preconditioned iterative linear solvers for some integrators. Numer. Linear Algebra with Appl. 8(2), 111-125 (2001). doi:10.1002/1099-1506(200103)8:2>111::AID-NLA234>3.0.CO;2-Q · Zbl 1051.65026
[5] Bertaccini, D.; Ng, MK, Block \(\omega \)-circulant preconditioners for the systems of differential equations, Calcolo., 40, 2, 71-90, 2003 · Zbl 1072.65044 · doi:10.1007/s100920300004
[6] Bini, D., Benedetto, F.: A new preconditioner for the parallel solution of positive definite Toeplitz systems. In Proc. Second ACM Symp. on Parallel Algorithms and Architectures, pp. 220-223 (1990). doi:10.1145/97444.97688
[7] Bini, D.; Capovani, M., Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl., 52, 99-126, 1983 · Zbl 0549.15005 · doi:10.1016/0024-3795(83)90009-5
[8] Brandts, JH; da Silva, RR, Computable eigenvalue bounds for rank-\(k\) perturbations, Linear Algebra Appl., 432, 12, 3100-3116, 2010 · Zbl 1195.15019 · doi:10.1016/j.laa.2010.02.010
[9] Chan, RH; Ng, MK, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 3, 427-482, 1996 · Zbl 0863.65013 · doi:10.1137/s0036144594276474
[10] Chan, TF, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comput., 9, 4, 766-771, 1988 · Zbl 0646.65042 · doi:10.1137/0909051
[11] Cocquet, PH; Gander, MJ, How large a shift is needed in the shifted Helmholtz preconditioner for its effective inversion by multigrid?, SIAM J. Sci. Stat. Comput., 39, 2, A438-A478, 2017 · Zbl 1365.65269 · doi:10.1137/15M102085X
[12] Danieli, F., Wathen, A.J.: All-at-once solution of linear wave equations. Numer. Linear Algebra with Appl. e2386 (2021). doi:10.1002/nla.2386 · Zbl 07478618
[13] Di Benedetto, F., Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM J. Sci. Comput., 16, 3, 682-697, 1995 · Zbl 0830.65032 · doi:10.1137/0916041
[14] Di Benedetto, F., Solution of Toeplitz normal equations by sine transform based preconditioning, Linear Algebra and Its Appl., 285, 1-3, 229-255, 1998 · Zbl 0935.65036 · doi:10.1016/s0024-3795(98)10115-5
[15] Di Benedetto, F.; Serra-Capizzano, S., A unifying approach to abstract matrix algebra preconditioning, Numer Math., 82, 57-90, 1999 · Zbl 0930.65050 · doi:10.1007/s002110050411
[16] Dobrev, V.A., Kolev, Tz., Petersson, N.A., Schroder, J.B.: Two-level convergence theory for multigrid reduction in time (MGRIT). SIAM J. Sci. Comput. 39(5), S501-S527 . doi:10.1137/16m1074096 · Zbl 1416.65329
[17] Donatelli, M.; Mazza, M.; Serra-Capizzano, S., Spectral analysis and structure preserving preconditioners for fractional diffusion equations, J. Comput. Phys., 307, 262-279, 2016 · Zbl 1352.65305 · doi:10.1016/j.jcp.2015.11.061
[18] Falgout, RD; Friedhoff, S.; Kolev, TV; MacLachlan, SP; Schroder, JB, Parallel time integration with multigrid, SIAM J. Sci. Comput., 36, 6, C635-C661, 2014 · Zbl 1310.65115 · doi:10.1002/pamm.201410456
[19] Ferrari, P.; Furci, I.; Hon, S.; Mursaleen, MA; Serra-Capizzano, S., The eigenvalue distribution of special 2-by-2 block matrix-sequences with applications to the case of symmetrized Toeplitz structures, SIAM J. Matrix Anal. Appl., 40, 3, 1066-1086, 2019 · Zbl 1426.15041 · doi:10.1137/18m1207399
[20] Gander, M.J.: 50 years of time parallel time integration. Multiple Shooting and Time Domain Decomposition Methods. In: Carraro, T., Geiger, M., S.Körkel, R.R. (eds.) 69-113. Springer, Cham (2015). doi:10.1007/978-3-319-23321-5_3 · Zbl 1337.65127
[21] Gander, M.J., Halpern, L., Ryan, J., Tran, T.T.B.: A direct solver for time parallelization. Domain Decomposition Methods in Science and Engineering XXII. In: Dickopf, T., Gander, M.J., Halpern, L., Krause, R., Pavarino, L.F. (eds.) 491-499. Springer, Cham (2016). doi:10.1007/978-3-319-18827-0_50 · Zbl 1339.65114
[22] Gander, MJ; Neumüller, M., Analysis of a new space-time parallel multigrid algorithm for parabolic problems, SIAM J. Sci. Comput., 38, 4, A2173-A2208, 2016 · Zbl 1342.65225 · doi:10.1137/15m1046605
[23] Gander, MJ; Vandewalle, S., Analysis of the parareal time-parallel time-integration method, SIAM J. Sci. Comput., 29, 2, 556-578, 2007 · Zbl 1141.65064 · doi:10.1137/05064607x
[24] Garoni, C., Serra-Capizzano, S.: Generalized Locally Toeplitz Sequences: Theory and Applications. Vol. 1, Springer, Cham (2017). doi:10.1007/978-3-319-53679-8_8 · Zbl 1376.15002
[25] Garoni, C., Serra-Capizzano, S.: Generalized Locally Toeplitz Sequences: Theory and Applications. Vol. 2, Springer, Cham (2018). doi:10.1007/978-3-030-02233-4 · Zbl 1448.47004
[26] Goddard, A.; Wathen, A., A note on parallel preconditioning for all-at-once evolutionary PDEs, Electron. Trans. Numer. Anal., 51, 135-150, 2019 · Zbl 1422.65232 · doi:10.1553/etna_vol51s135
[27] Hon, S.: Optimal block circulant preconditioners for block Toeplitz systems with application to evolutionary PDEs. J. Comput. Appl. Math. 407, 113965 (2021). doi:10.1016/j.cam.2021.113965 · Zbl 1490.65046
[28] Hon, S., Serra-Capizzano, S., Wathen, A.: Band-Toeplitz preconditioners for ill-conditioned Toeplitz systems. BIT Numer. Math. (2021). doi:10.1007/s10543-021-00889-6 · Zbl 1498.65041
[29] Horton, G.; Vandewalle, S., A space-time multigrid method for parabolic partial differential equations, SIAM J. Sci. Comput., 16, 4, 848-864, 1995 · Zbl 0828.65105 · doi:10.1137/0916050
[30] Lin, XL; Ng, MK, An all-at-once preconditioner for evolutionary partial differential equations, SIAM J. Sci. Comput., 43, 4, A2766-A2784, 2021 · Zbl 07379636 · doi:10.1137/20m1316354
[31] Lin, XL; Ng, MK; Zhi, Y., A parallel-in-time two-sided preconditioning for all-at-once system from a non-local evolutionary equation with weakly singular kernel, J. Comput. Phys., 434, 2021 · Zbl 07508529 · doi:10.1016/j.jcp.2021.110221
[32] Lions, J.L., Maday, Y., Turinici, G.: A “parareal” in time discretization of PDE’s. Comptes rendus de l’Académie des sciences. Série 1, Mathématique 332(7), 661-668 (2001) · Zbl 0984.65085
[33] Liu, J.; Wu, SL, A fast block \(\alpha \)-circulant preconditioner for all-at-once systems from wave equations, SIAM J. Matrix Analysis and Appl., 41, 4, 1912-1943, 2021 · Zbl 1460.65102 · doi:10.1137/19m1309869
[34] Mazza, M.; Pestana, J., Spectral properties of flipped Toeplitz matrices and related preconditioning, BIT Numer. Math., 59, 463-482, 2018 · Zbl 1417.15045 · doi:10.1007/s10543-018-0740-y
[35] McDonald, E., Hon, S., Pestana, J., Wathen, A.: Preconditioning for nonsymmetry and time-dependence. In Lecture Notes in Comput. Sci. Eng. 116, 81-91 (2017). Springer International Publishing. doi:10.1007/978-3-319-52389-7_7 · Zbl 1367.65045
[36] McDonald, E.; Pestana, J.; Wathen, A., Preconditioning and iterative solution of all-at-once systems for evolutionary partial differential equations, SIAM J. Sci. Comput., 40, 2, A1012-A1033, 2018 · Zbl 1392.65036 · doi:10.1137/16m1062016
[37] Ng, MK, Iterative Methods for Toeplitz Systems, 2004, New York: Numerical Mathematics and Scientific Computation. Oxford University Press, New York · Zbl 1059.65031 · doi:10.1093/oso/9780198504207.001.0001
[38] Ng, MK; Pan, J., Approximate inverse circulant-plus-diagonal preconditioners for Toeplitz-plus-diagonal matrices, SIAM J. Sci. Comput., 32, 3, 1442-1464, 2010 · Zbl 1222.65028 · doi:10.1137/080720280
[39] Serra-Capizzano, S., The GLT class as a generalized Fourier analysis and applications, Linear Algebra and Its Appl., 419, 1, 180-233, 2006 · Zbl 1109.65032 · doi:10.1016/j.laa.2006.04.012
[40] Serra-Capizzano, S., Toeplitz preconditioners constructed from linear approximation processes, SIAM J. Matrix Analysis and Appl., 20, 2, 446-465, 1999 · Zbl 0919.65031 · doi:10.1137/s0895479897316904
[41] Serra-Capizzano, S., Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear. Special issue on structured and infinite systems of linear equations., Linear Algebra Appl., 343, 344, 303-319, 2002 · Zbl 1001.65041 · doi:10.1016/S0024-3795(01)00361-5
[42] Serra-Capizzano, S.; Tilli, P., On unitarily invariant norms of matrix-valued linear positive operators, J. Inequalities and App., 7, 3, 309-330, 2002 · Zbl 1055.15039 · doi:10.1155/s1025583402000152
[43] Serra-Capizzano, S.; Tyrtyshnikov, E., How to prove that a preconditioner cannot be superlinear, Math. Comput., 72, 243, 1305-1316, 2003 · Zbl 1021.15005 · doi:10.1090/s0025-5718-03-01506-0
[44] Strang, G., A proposal for Toeplitz matrix calculations, Stud. Appl. Math., 74, 2, 171-176, 1986 · Zbl 0621.65025 · doi:10.1002/sapm1986742171
[45] Wathen, A., Preconditioning, Acta Numerica., 24, 329-376, 2015 · Zbl 1316.65039 · doi:10.1017/s0962492915000021
[46] Wu, S.L., Zhou, T.: Parallel implementation for the two-stage SDIRK methods via diagonalization. J. Comput. Phys. 428, 110076 (2021). doi:10.1016/j.jcp.2020.110076 · Zbl 07511430
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.