Any circulant-like preconditioner for multilevel matrices is not superlinear

Superlinear preconditioners (those that provide a proper cluster at 1) are very important for the cg-like methods since they make these methods converge superlinearly. As is well known, for Toeplitz matrices generated by a continuous symbol, many circulant and circulant-like (related to different matrix algebras) preconditioners were proved to be superlinear. In contrast, for multilevel Toeplitz matrices there has been no proof of the superlinearity of any multilevel circulants. In this paper we show that such a proof is not possible since any multilevel circulant preconditioner is not superlinear, in the general case of multilevel Toeplitz matrices. Moreover, for matrices not necessarily Toeplitz, we present some general results proving that many popular structured preconditioners cannot be superlinear.