Toeplitz and Block-Toeplitz Structures with Variants: from the Spectral Analysis to Preconditioning and Multigrid Methods Using a Symbol Approach

A great deal of real-world applications requires the solution of a Partial Differential Equation (PDE). However, this kind of continuous equation often does not admit an analytical solution, which needs to be approximated by means of a numerical method. If the PDE and the numerical method are both linear, the computation of the numerical solution reduces to solving a sequence of linear systems with increasing dimensions, whose matrix of coefficients is often a structured matrix-sequence with a certain type of either time or space invariance. The latter facts constitute the main motivation for the thesis, which is focused on the study of Toeplitz-related matrices. In particular, the thesis contains the results of three main research lines. The first part regards the development of suitable solution strategies for linear systems with non-symmetric real Toeplitz coefficient matrices. The resulting algorithm is a preconditioned MINRES method applied to a symmetrized linear system. The second part of the thesis consists in the theoretical study of algebraic multigrid methods for block-Toeplitz linear systems. Finally, we consider the space-time discretization of the anisotropic diffusion equation, using an isogeometric analysis approximation in space and a discontinuous Galerkin approximation in time, and we construct a competitive solver in terms of robustness, run-time and parallel scaling. For all the three topics the concept of spectral symbol plays a crucial role.