Preconditioners for symmetrized Toeplitz and multilevel Toeplitz matrices

Research output: Contribution to journalArticle

Abstract

When solving linear systems with nonsymmetric Toeplitz or multilevel Toeplitz matrices using Krylov subspace methods, the coefficient matrix may be symmetrized. The preconditioned MINRES method can then be applied to this symmetrized system, which allows rigorous upper bounds on the number of MINRES iterations to be obtained. However, effective preconditioners for symmetrized (multilevel) Toeplitz matrices are lacking. Here, we propose novel ideal preconditioners, and investigate the spectra of the preconditioned matrices. We show how these preconditioners can be approximated and demonstrate their effectiveness via numerical experiments.
LanguageEnglish
Pages870-887
Number of pages18
JournalSIAM Journal on Matrix Analysis and Applications
Volume40
Issue number3
DOIs
Publication statusPublished - 16 Jul 2019

Fingerprint

Toeplitz matrix
Otto Toeplitz
MINRES
Preconditioner
Krylov Subspace Methods
Linear Systems
Numerical Experiment
Upper bound
Iteration
Coefficient
Demonstrate

Keywords

  • Toeplitz matrix
  • multilevel Toeplitz matrix
  • symmetrization
  • preconditioning
  • Krylov subspace method

Cite this

@article{8b6e647dbd244214b3f40ada9a020d5f,
title = "Preconditioners for symmetrized Toeplitz and multilevel Toeplitz matrices",
abstract = "When solving linear systems with nonsymmetric Toeplitz or multilevel Toeplitz matrices using Krylov subspace methods, the coefficient matrix may be symmetrized. The preconditioned MINRES method can then be applied to this symmetrized system, which allows rigorous upper bounds on the number of MINRES iterations to be obtained. However, effective preconditioners for symmetrized (multilevel) Toeplitz matrices are lacking. Here, we propose novel ideal preconditioners, and investigate the spectra of the preconditioned matrices. We show how these preconditioners can be approximated and demonstrate their effectiveness via numerical experiments.",
keywords = "Toeplitz matrix, multilevel Toeplitz matrix, symmetrization, preconditioning, Krylov subspace method",
author = "J. Pestana",
year = "2019",
month = "7",
day = "16",
doi = "10.1137/18M1205406",
language = "English",
volume = "40",
pages = "870--887",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
number = "3",

}

Preconditioners for symmetrized Toeplitz and multilevel Toeplitz matrices. / Pestana, J.

In: SIAM Journal on Matrix Analysis and Applications, Vol. 40, No. 3, 16.07.2019, p. 870-887.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Preconditioners for symmetrized Toeplitz and multilevel Toeplitz matrices

AU - Pestana, J.

PY - 2019/7/16

Y1 - 2019/7/16

N2 - When solving linear systems with nonsymmetric Toeplitz or multilevel Toeplitz matrices using Krylov subspace methods, the coefficient matrix may be symmetrized. The preconditioned MINRES method can then be applied to this symmetrized system, which allows rigorous upper bounds on the number of MINRES iterations to be obtained. However, effective preconditioners for symmetrized (multilevel) Toeplitz matrices are lacking. Here, we propose novel ideal preconditioners, and investigate the spectra of the preconditioned matrices. We show how these preconditioners can be approximated and demonstrate their effectiveness via numerical experiments.

AB - When solving linear systems with nonsymmetric Toeplitz or multilevel Toeplitz matrices using Krylov subspace methods, the coefficient matrix may be symmetrized. The preconditioned MINRES method can then be applied to this symmetrized system, which allows rigorous upper bounds on the number of MINRES iterations to be obtained. However, effective preconditioners for symmetrized (multilevel) Toeplitz matrices are lacking. Here, we propose novel ideal preconditioners, and investigate the spectra of the preconditioned matrices. We show how these preconditioners can be approximated and demonstrate their effectiveness via numerical experiments.

KW - Toeplitz matrix

KW - multilevel Toeplitz matrix

KW - symmetrization

KW - preconditioning

KW - Krylov subspace method

UR - https://www.siam.org/Publications/Journals/SIAM-Journal-on-Matrix-Analysis-and-Applications-SIMAX

U2 - 10.1137/18M1205406

DO - 10.1137/18M1205406

M3 - Article

VL - 40

SP - 870

EP - 887

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 - 3

ER -