How to prove that a preconditioner cannot be superlinear

In the general case of multilevel Toeplitz matrices, we recently proved that any multilevel circulant preconditioner is not superlinear (a cluster it may provide cannot be proper). The proof was based on the concept of quasi-equimodular matrices, although this concept does not apply, for example, to...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of computation 2003-07, Vol.72 (243), p.1305-1316
Main Authors: Capizzano, S. Serra, Tyrtyshnikov, E.
Format: Article
Language:English
Subjects:
Algebra
Algebraic conjugates
Approximation
Linear algebra
Mathematical theorems
Matrices
Polynomials
Preconditioning
Zero
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the general case of multilevel Toeplitz matrices, we recently proved that any multilevel circulant preconditioner is not superlinear (a cluster it may provide cannot be proper). The proof was based on the concept of quasi-equimodular matrices, although this concept does not apply, for example, to the sine-transform matrices. In this paper, with a new concept of \textit{partially equimodular} matrices, we cover all trigonometric matrix algebras widely used in the literature. We propose a technique for proving the non-superlinearity of certain frequently used preconditioners for some representative sample multilevel matrices. At the same time, we show that these preconditioners are, in a certain sense, the best among the sublinear preconditioners (with only a general cluster) for multilevel Toeplitz matrices.
ISSN:0025-5718
1088-6842
DOI:10.1090/S0025-5718-03-01506-0