Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear

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 A={A(N)}(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)σi=1 dni -1) for any matrix sequence P={P(N)}∈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.