TY - JOUR
T1 - An All-at-Once Preconditioner for Evolutionary Partial Differential Equations
AU - Lin, Xue Lei
AU - Ng, Michael
N1 - Funding information:
This work was supported by HKRGC GRF through grants 12200317, 12300218, 12300519, and 17201020, by the NSFC through grant 11801479, and by NSAF through grant U1930402.
Publisher Copyright:
© 2021 Society for Industrial and Applied Mathematics
PY - 2021/1
Y1 - 2021/1
N2 - In [McDonald, Pestana, and Wathen, SIAM J. Sci. Comput., 40 (2018), pp. A1012--A1033], a block circulant preconditioner is proposed for all-at-once linear systems arising from evolutionary partial differential equations, in which the preconditioned matrix is proven to be diagonalizable and to have identity-plus-low-rank decomposition in the case of the heat equation. In this paper, we generalize the block circulant preconditioner by introducing a small parameter 𝜖>0 into the top-right block of the block circulant preconditioner. The implementation of the generalized preconditioner requires the same computational complexity as that of the block circulant one. Theoretically, we prove that (i) the generalization preserves the diagonalizability and the identity-plus-low-rank decomposition; (ii) all eigenvalues of the new preconditioned matrix are clustered at 1 for sufficiently small 𝜖; (iii) GMRES method for the preconditioned system has a linear convergence rate independent of size of the linear system when 𝜖 is taken to be smaller than or comparable to square root of time-step size. Numerical results are reported to confirm the efficiency of the proposed preconditioner and to show that the generalization improves the performance of block circulant preconditioner.
AB - In [McDonald, Pestana, and Wathen, SIAM J. Sci. Comput., 40 (2018), pp. A1012--A1033], a block circulant preconditioner is proposed for all-at-once linear systems arising from evolutionary partial differential equations, in which the preconditioned matrix is proven to be diagonalizable and to have identity-plus-low-rank decomposition in the case of the heat equation. In this paper, we generalize the block circulant preconditioner by introducing a small parameter 𝜖>0 into the top-right block of the block circulant preconditioner. The implementation of the generalized preconditioner requires the same computational complexity as that of the block circulant one. Theoretically, we prove that (i) the generalization preserves the diagonalizability and the identity-plus-low-rank decomposition; (ii) all eigenvalues of the new preconditioned matrix are clustered at 1 for sufficiently small 𝜖; (iii) GMRES method for the preconditioned system has a linear convergence rate independent of size of the linear system when 𝜖 is taken to be smaller than or comparable to square root of time-step size. Numerical results are reported to confirm the efficiency of the proposed preconditioner and to show that the generalization improves the performance of block circulant preconditioner.
KW - All-at-once discretization
KW - Block Toeplitz matrices
KW - Convergence of GMRES
KW - Evolutionary equations
KW - Preconditioning technique
UR - http://www.scopus.com/inward/record.url?scp=85112403938&partnerID=8YFLogxK
U2 - 10.1137/20M1316354
DO - 10.1137/20M1316354
M3 - Journal article
AN - SCOPUS:85112403938
SN - 1064-8275
VL - 43
SP - A2766-A2784
JO - SIAM Journal on Scientific Computing
JF - SIAM Journal on Scientific Computing
IS - 4
ER -