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.

Band-Toeplitz preconditioners for ill-conditioned Toeplitz systems

Serra Capizzano S.;
2021-01-01

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.
2021
BIT
Band-Toeplitz/circulant preconditioners; Block matrices; Fractional diffusion equations; Krylov subspace methods; Singular value/eigenvalue distribution; Toeplitz/Hankel matrices
Hon, S.; Serra Capizzano, S.; Wathen, A.
File in questo prodotto:
File Dimensione Formato  
Hon2021_Article_Band-ToeplitzPreconditionersFo.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: DRM non definito
Dimensione 635.49 kB
Formato Adobe PDF
635.49 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/2119497
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 6
social impact