A block $α$-circulant based preconditioned MINRES method for wave equations

In this work, we propose an absolute value block $\alpha$-circulant preconditioner for the minimal residual (MINRES) method to solve an all-at-once system arising from the discretization of wave equations. Since the original block $\alpha$-circulant preconditioner shown successful by many recently is non-Hermitian in general, it cannot be directly used as a preconditioner for MINRES. Motivated by the absolute value block circulant preconditioner proposed in [E. McDonald, J. Pestana, and A. Wathen. SIAM J. Sci. Comput., 40(2):A1012-A1033, 2018], we propose an absolute value version of the block $\alpha$-circulant preconditioner. Our proposed preconditioner is the first Hermitian positive definite variant of the block $\alpha$-circulant preconditioner, which fills the gap between block $\alpha$-circulant preconditioning and the field of preconditioned MINRES solver. The matrix-vector multiplication of the preconditioner can be fast implemented via fast Fourier transforms. Theoretically, we show that for properly chosen $\alpha$ the MINRES solver with the proposed preconditioner has a linear convergence rate independent of the matrix size. To the best of our knowledge, this is the first attempt to generalize the original absolute value block circulant preconditioner in the aspects of both theory and performance. Numerical experiments are given to support the effectiveness of our preconditioner, showing that the expected optimal convergence can be achieved.