Multigrid Methods for Strongly Ill-Conditioned Structured Matrices

Multigrid methods are highly efficient solution techniques for large sparse linear systems which are positive definite and ill-conditioned. Matrices belonging to the two-level Toeplitz class or to one of the two-level trigonometric matrix algebras are associated with generating functions. In this paper, we develop multigrid methods for linear systems which correspond to generating functions with whole zero curves. For functions with isolated zeros several multigrid methods are well-known, but the case of zero curves is significantly more difficult. First, we develop a two-grid method based on the Galerkin approach, extending results from the isolated zero case. We prove two-grid convergence, and describe why a Galerkin-based multigrid method is not practical. Instead, we use a rediscretization technique which is based on a sufficiently accurate approximation of the zero curve on the coarse grid. With this approach the same convergence behavior as for the Galerkin method is obtained, but matrices remain sparse on coarser levels, allowing several levels to be used. Key words: multilevel Toeplitz, trigonometric matrix algebras, multigrid methods, iterative methods PACS: