Multigrid methods for (multilevel) structured matrices associated with a symbol and related applications

When dealing with large linear systems with a prescribed structure, two key ingredients are important for designing fast solvers: the first is the computational analysis of the structure which is usually inherited from an underlying infinite dimensional problem, the second is the spectral analysis which is often deeply related to a compact symbol, again depending on the infinite dimensional problem of which the linear system is a given approximation. When considering the computational viewpoint, the first ingredient is useful for designing fast matrix-vector multiplication algorithms, while the second ingredient is essential for designing fast iterative solvers (multigrid, preconditioned Krylov etc), whose convergence speed is optimal in the Axelsson, Neytcheva sense, i.e., the number of iterations for reaching a preassigned accuracy can be bounded by a pure constant independent of the matrix-size. In this review paper we consider in some details the specific case of multigrid-type techniques for Toeplitz related structures, by emphasizing the role of the structure and of the compact spectral symbol. A sketch of several extensions to other (hidden) structures as those appearing in the numerical approximation of partial differential equations and integral equations is given and critically discussed.