Multigrid Preconditioning and Toeplitz Matrices

Thomas Huckle
TU Munchen, Institut für Informatik
Arcisstr. 21, D-80290 Munchen, Germany


In this paper we discuss Multigrid methods for Toeplitz matrices. Then the restriction and prolongation operator can be seen as projected Toeplitz matrices. Because of the intimate connection between such matrices and trigonometric series we can express the Multigrid algorithm in terms of the underlying functions with special zeroes. This shows how to choose the prolongation/restriction operator in order to get fast convergence. This approach allows Multigrid methods for general Toeplitz systems as long as we have some information on the underlying function. Furthermore, we can define projections not only on problems of half size n/2 , but on every size n/m for any m that is a natural number. We can apply the derived method also to the constant-coefcient case for PDE on simple regions, e.g., in connection with the Helmholtz equation or Convection-Diffusion equation.

Key words: multigrid methods, preconditioning, Toeplitz matrices