Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate (Q598222)

In the past two decades many papers from the literature deal with the solution of multilevel Toeplitz systems because of several applications: signal prosessing, image restoration, partial differential equations, time series. Futhermore, multilevel Toeplitz matrices are interesting from the viewpoint of complexity theory. A good idea for solving such linear systems is by using iterative solvers in which the involved matrices preserve a Toeplitz structure (for example gradient methods, Chebyshev iterations, Jacobi or Richardson methods). In this paper the authors show that the multilevel Toeplitz case is dramatically different from the scalar Toeplitz case in terms of preconditioning using fast transform algebras, that is, in multilevel case it is impossible to find superlinear and/or spectrally equivalent matrix algebra preconditioners. The optimality is proved in the case of multilevel band Toeplitz preconditioning.