Circulant preconditioners with unbounded inverses
type: Item
instance of: scholarly article
title: Circulant preconditioners with unbounded inverses
zbMATH Open document ID: 0821.65013
DOI: 10.1016/0024-3795(93)00092-E
published in: Linear Algebra and its Applications
publication date: 1995-06-12T00:00:00Z
review text: Let \(A_ n = [a_{i-j}]\) be a Hermitian Toeplitz matrix whose entries are the Fourier coefficients of a function \(f\). The quality of a preconditioner \(M_ n\) is measured by how well the singular values of \(M_ n^{-1} A_ n\) cluster at 1. This clustering has been proved for \(M_ n = C_ n\) and \(M_ n = S_ n\) (the optimal and the simplified circulant preconditioners) under the condition that \(\sum | a_ k | < \infty\) and \(\inf f(x) = \delta > 0\). In this paper, such a clustering property is proved under the weaker condition that \(f\in L_ 2\) and that \(f(x)\) is in a sense sparsely vanishing, i.e., the set where \(f(x) = 0\) is small. Since the preconditioners may become singular (unbounded inverses) or indefinite, they can be replaced with improved preconditioners by replacing the undesired eigenvalues by positive ones. Estimates are given for \(\gamma_ n (\varepsilon)\), the number of eigenvalues which do not cluster in an \(\varepsilon\)-neighbourhood of 1. The growth of \(\gamma_ n (\varepsilon)\) with \(n\) depends on the smoothness of the function \(f\) but only in the case of the simplified preconditioner. Enhancing smoothness has no influence on \(\gamma_ n (\varepsilon)\) for \(C_ n\). It is not known how sharp the given estimates for \(\gamma_ n (\varepsilon)\) are. The corresponding results for multilevel Toeplitz matrices are readily obtained from the previous analysis and are mainly summarized in the last section.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65F35
Mathematics Subject Classification ID: 15A12
zbMATH DE Number: 753878
zbMATH Keywords: circulant preconditioners
zbMATH Keywords: iterative solution of Toeplitz systems
zbMATH Keywords: unbounded inverses
zbMATH Keywords: Hermitian Toeplitz matrix
zbMATH Keywords: Fourier coefficients
zbMATH Keywords: singular values
zbMATH Keywords: eigenvalues
zbMATH Keywords: multilevel Toeplitz matrices
author: E. E. Tyrtyshnikov
MaRDI profile type: Publication
cites work: On bilinear forms in Gaussian random variables and Toeplitz matrices
cites work: On the rate of convergence of the preconditioned conjugate gradient method
cites work: Circulant Preconditioners for Hermitian Toeplitz Systems
cites work: A Family of Block Preconditioners for Block Systems
cites work: Circulant Preconditioners for Complex Toeplitz Matrices
cites work: An Optimal Circulant Preconditioner for Toeplitz Systems
cites work: Circulant and Skewcirculant Matrices for Solving Toeplitz Matrix Problems
cites work: Q3359644
cites work: Q3247378
cites work: On the distribution of the singular values of Toeplitz matrices
cites work: A Proposal for Toeplitz Matrix Calculations
cites work: Optimal and Superoptimal Circulant Preconditioners
cites work: A unifying approach to some old and new theorems on distribution and clustering
cites work: Q4001452
cites work: Q5674306
description: scientific article; zbMATH DE number 753878