Preconditioners for nondefinite Hermitian Toeplitz systems

Chan, Raymond H. ; Potts, Daniel ; Steidl, Gabriele

1999_242.pdf - Published

Download (1MB)

URN: urn:nbn:de:bsz:180-madoc-20627
Document Type: Working paper
Year of publication: 1999
Publication language: English
Institution: School of Business Informatics and Mathematics > Sonstige - Fakultät für Mathematik und Informatik
MADOC publication series: Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Mathematik > Mannheimer Manuskripte
Subject: 510 Mathematics
Classification: MSC: 65F35 65F10 65Y20 65T50 ,
Subject headings (SWD): Toeplitz-Matrix , Krylov-Verfahren , Trigonometrie
Keywords (English): nondefinite Toeplitz matrices , circulant matrices , Krylov space methods , circulant preconditioners , minimal residual method , algorithm
Abstract: This paper is concerned with the construction of circulant preconditioners for Toeplitz systems arising from a piecewise continuous generating function with sign changes. If the generating function is given, we prove that for any Σ > 0, only Ο(log N) eigenvalues of our preconditioned Toeplitz systems of size N x N are not contained in [-1- Σ, -1+Σ]U [1-Σ, 1+Σ]. The result can be modified for trigonometric preconditioners. We also suggest circulant preconditioners for the case that the generating function is not explicitly known and show that only Ο(log N) absolute values of the eigenvalues of the preconditioned Toeplitz systems are not contained in a positive interval on the real axis. Using the above results, we conclude that the preconditioned minimal residual method requires only Ο(N log² N) arithmetical operations to achive a solution of prescribed precision if the spectral condition numbers of the Toeplitz systems increase at most polynomial in N. We present various numerical tests.
Additional information:

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.

Metadata export


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item