Spectral equivalence and matrix algebra preconditioners for multilevel Toeplitz systems: a negative result

In the last two decades a lot of matrix algehra optimal and superlinear preconditioners (those assuring a strong clustering at the unity) have been proposed for the solution of polynomially ill-conditioned Toeplitz linear systems. The corresponding generalizations to multilevel structures do not preserve optimality neither superlinearity. Regarding the notion of superlinearity, it has been recently shown that this is simply impossible. Here we propose some ideas and a proof technique for demonstrating that also the spectral equivalence and the essential spectral equivalence (up to a constant number of diverging eigenvalues) are impossible and therefore the search for optimal matrix algebra preconditioners in the multilevel setting cannot be successful.