Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear

By Stefano Serra Capizzano. 2002

58 citations recorded by the source corpus.

Let f be a d-variate 2π periodic continuous function and let {Tn(f )}n, n = (n1 ,...,n d ), be the multiindexed sequence of multilevel N × N Toeplitz matrices (N = N(n) = � i ni ) generated by f. Let A ={ AN }N be a sequence of matrix algebras simultaneously diagonalized by unitary transforms. We show that there exist infinitely many linearly independent trigonometric polynomials (and continuous nonpolynomial functions) f such that rank� (Tn(f ) − PN )/ = o(N (n) � d=1 n −1 i ) for any matrix sequence P ={ PN }∈ A. This implies that no superlinear matrix algebra preconditioner exists in the multilevel Toeplitz case. The above mentioned result improves the analysis of the author and E. Tyrtyshnikov [SIAM J. Matrix Anal. Appl. 21 (2) (1999) 431] where the same was proved under the assumption that the involved algebras are of circulant type. © 2002 Elsevier Science Inc. All rights reserved.

Subfields: Algebra and Number Theory, Applied Mathematics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/9c1946a90996c6d7727a9925cd10f5400deaac2a