Circulant preconditioners with unbounded inverses (Q1805211)

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.