Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear Original Research Article

Let f be a d-variate 2π periodic continuous function and let {Tn(f)}n, n=(n1,…,nd), be the multiindexed sequence of multilevel N×N Toeplitz matrices (N=N(n)=∏ini) generated by f. Let image 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)∑i=1dni−1) for any matrix sequence image . 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.