Author
Hon, S
Serra-Capizzano, S
Wathen, A
Journal title
BIT Numerical Mathematics
DOI
10.1007/s10543-021-00889-6
Issue
2
Volume
62
Last updated
2022-08-09T12:42:13.18+01:00
Page
465-491
Abstract
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(nlog⁡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.
Symplectic ID
1191761
Favourite
Off
Publication type
Journal Article
Publication date
09 Aug 2021
Please contact us for feedback and comments about this page. Created on 20 Aug 2021 - 15:38.