Band-Toeplitz preconditioners for ill-conditioned Toeplitz systems

Sean Hon*, Stefano Serra-Capizzano, Andy Wathen

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

6 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)465–491
Number of pages27
JournalBIT Numerical Mathematics
Volume62
Issue number2
Early online date9 Aug 2021
DOIs
Publication statusPublished - Jun 2022

Scopus Subject Areas

  • Software
  • Computer Networks and Communications
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Band-Toeplitz/circulant preconditioners
  • Block matrices
  • Fractional diffusion equations
  • Krylov subspace methods
  • Singular value/eigenvalue distribution
  • Toeplitz/Hankel matrices

Fingerprint

Dive into the research topics of 'Band-Toeplitz preconditioners for ill-conditioned Toeplitz systems'. Together they form a unique fingerprint.

Cite this