Band-Toeplitz preconditioners for ill-conditioned Toeplitz systems

• Published in: BIT 2022-06, Vol.62 (2), p.465-491
• Main Authors: Hon, Sean, Serra-Capizzano, Stefano, Wathen, Andy
• Format: Article
• Language: English
• Subjects: Computational Mathematics and Numerical Analysis; Convergence; Diffusion barriers; Eigenvalues; Mathematical analysis; Mathematics; Mathematics and Statistics; Numeric Computing; Permutations; Preconditioning
• ISSN: 0006-3835; 1572-9125; 1572-9125
• DOI: 10.1007/s10543-021-00889-6

Preconditioning for Toeplitz systems has been an active research area over the past few decades. Along this line of research, circulant preconditioners have been recently proposed for the Toeplitz-like system arising from discretizing fractional diffusion equations. A common approach is to combine a circulant preconditioner with the preconditioned conjugate gradient normal residual (PCGRN) method for the coefficient system. In this work, instead of using PCGRN for the normal equation system, we propose a simple yet effective preconditioning approach for solving the original system using the preconditioned minimal residual (PMINRES) method that can achieve convergence guarantees depending only on eigenvalues. Namely, for a large class of ill-conditioned Toeplitz systems, we propose a number of preconditioners that attain the overall O ( n log n ) complexity. We first symmetrize the given Toeplitz system by using a permutation matrix and construct a band-Toeplitz plus circulant preconditioner for the modified system. Then, under certain assumptions, we show that the eigenvalues of the preconditioned system are clustered around ± 1 except a number of outliers and hence superlinear convergence rate of PMINRES can be achieved. Particularly, we indicate that our solver can be applied to solve certain fractional diffusion equations. An extension of this work to the block Toeplitz case is also included. Numerical examples are provided to demonstrate the effectiveness of our proposed method.