A preconditioned MINRES method for nonsymmetric Toeplitz matrices

J. Pestana, A. J. Wathen

Research output: Contribution to journalArticle

14 Citations (Scopus)

Abstract

Circulant preconditioning for symmetric Toeplitz linear systems is well established; theoretical guarantees of fast convergence for the conjugate gradient method are descriptive of the convergence seen in computations. This has led to robust and highly efficient solvers based on use of the fast Fourier transform exactly as originally envisaged in [G. Strang, Stud. Appl. Math., 74 (1986), pp. 171--176]. For nonsymmetric systems, the lack of generally descriptive convergence theory for most iterative methods of Krylov type has provided a barrier to such a comprehensive guarantee, though several methods have been proposed and some analysis of performance with the normal equations is available. In this paper, by the simple device of reordering, we rigorously establish a circulant preconditioned short recurrence Krylov subspace iterative method of minimum residual type for nonsymmetric (and possibly highly nonnormal) Toeplitz systems. Convergence estimates similar to those in the symmetric case are established.
LanguageEnglish
Pages273-288
Number of pages16
JournalSIAM Journal on Matrix Analysis and Applications
Volume36
Issue number1
DOIs
Publication statusPublished - 19 Mar 2015

Fingerprint

MINRES
Toeplitz System
Nonsymmetric Matrix
Toeplitz matrix
Iteration
Normal Equations
Convergence Estimates
Subspace Methods
Krylov Subspace
Convergence Theory
Reordering
Conjugate Gradient Method
Fast Fourier transform
Preconditioning
Recurrence
Strings
Linear Systems

Keywords

  • circulant preconditioner
  • MINRES
  • nonsymmetric matrix
  • Toeplitz matrix

Cite this

@article{bacccf2f36e44f79802e303fcd90fe34,
title = "A preconditioned MINRES method for nonsymmetric Toeplitz matrices",
abstract = "Circulant preconditioning for symmetric Toeplitz linear systems is well established; theoretical guarantees of fast convergence for the conjugate gradient method are descriptive of the convergence seen in computations. This has led to robust and highly efficient solvers based on use of the fast Fourier transform exactly as originally envisaged in [G. Strang, Stud. Appl. Math., 74 (1986), pp. 171--176]. For nonsymmetric systems, the lack of generally descriptive convergence theory for most iterative methods of Krylov type has provided a barrier to such a comprehensive guarantee, though several methods have been proposed and some analysis of performance with the normal equations is available. In this paper, by the simple device of reordering, we rigorously establish a circulant preconditioned short recurrence Krylov subspace iterative method of minimum residual type for nonsymmetric (and possibly highly nonnormal) Toeplitz systems. Convergence estimates similar to those in the symmetric case are established.",
keywords = "circulant preconditioner, MINRES, nonsymmetric matrix, Toeplitz matrix",
author = "J. Pestana and Wathen, {A. J.}",
year = "2015",
month = "3",
day = "19",
doi = "10.1137/140974213",
language = "English",
volume = "36",
pages = "273--288",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
number = "1",

}

A preconditioned MINRES method for nonsymmetric Toeplitz matrices. / Pestana, J.; Wathen, A. J.

In: SIAM Journal on Matrix Analysis and Applications, Vol. 36, No. 1, 19.03.2015, p. 273-288.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A preconditioned MINRES method for nonsymmetric Toeplitz matrices

AU - Pestana, J.

AU - Wathen, A. J.

PY - 2015/3/19

Y1 - 2015/3/19

N2 - Circulant preconditioning for symmetric Toeplitz linear systems is well established; theoretical guarantees of fast convergence for the conjugate gradient method are descriptive of the convergence seen in computations. This has led to robust and highly efficient solvers based on use of the fast Fourier transform exactly as originally envisaged in [G. Strang, Stud. Appl. Math., 74 (1986), pp. 171--176]. For nonsymmetric systems, the lack of generally descriptive convergence theory for most iterative methods of Krylov type has provided a barrier to such a comprehensive guarantee, though several methods have been proposed and some analysis of performance with the normal equations is available. In this paper, by the simple device of reordering, we rigorously establish a circulant preconditioned short recurrence Krylov subspace iterative method of minimum residual type for nonsymmetric (and possibly highly nonnormal) Toeplitz systems. Convergence estimates similar to those in the symmetric case are established.

AB - Circulant preconditioning for symmetric Toeplitz linear systems is well established; theoretical guarantees of fast convergence for the conjugate gradient method are descriptive of the convergence seen in computations. This has led to robust and highly efficient solvers based on use of the fast Fourier transform exactly as originally envisaged in [G. Strang, Stud. Appl. Math., 74 (1986), pp. 171--176]. For nonsymmetric systems, the lack of generally descriptive convergence theory for most iterative methods of Krylov type has provided a barrier to such a comprehensive guarantee, though several methods have been proposed and some analysis of performance with the normal equations is available. In this paper, by the simple device of reordering, we rigorously establish a circulant preconditioned short recurrence Krylov subspace iterative method of minimum residual type for nonsymmetric (and possibly highly nonnormal) Toeplitz systems. Convergence estimates similar to those in the symmetric case are established.

KW - circulant preconditioner

KW - MINRES

KW - nonsymmetric matrix

KW - Toeplitz matrix

UR - http://epubs.siam.org/doi/10.1137/140974213

U2 - 10.1137/140974213

DO - 10.1137/140974213

M3 - Article

VL - 36

SP - 273

EP - 288

JO - SIAM Journal on Matrix Analysis and Applications

T2 - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 1

ER -