A Uniform Spectral Analysis for a Preconditioned All-at-Once System from First-Order and Second-Order Evolutionary Problems
Shu‐Lin Wu, Tao Zhou, Zhi Zhou
Abstract
Solving evolutionary equations in a parallel-in-time manner is an attractive topic. The iterative algorithm based on the block $\alpha$-circulant preconditioning technique has shown promising advantages, especially for hyperbolic problems. By fast Fourier transform for factorizing the involved circulant matrices, the preconditioned iteration can be computed efficiently via the so-called diagonalization technique, which yields a direct parallel implementation across all time levels. In recent years, considerable efforts have been devoted to exploring the spectral property of the iteration matrix arising from the used time-integrator, which leads to many case-by-case studies. Denoting by $\mathcal{K} $ and $\mathcal{P}_\alpha$ the all-at-once matrix of the evolutionary PDEs and the corresponding block $\alpha$-circulant preconditioner, we will present a systematic spectral analysis for the matrix $\mathcal{P}_\alpha^{-1}\mathcal{K}$ for both the first-order and second-order evolutionary problems. For the first-order problems our analysis works for all stable single-step time-integrators, while for the second-order problems our analysis works for a large class of symmetric two-step methods which could be arbitrarily high-order. Illustrative numerical experiments are presented to complement our theory.