Structured Matrices, Multigrid Methods, and the Helmholtz Equation

Discretization of the Helmholtz equation with certain boundary conditions results in structured linear systems which are associated with generating functions. Depending on the type of bound-ary conditions one obtains matrices of a certain class. By solving these systems with normal equations, we have the advantage that the corresponding generating functions are nonnegative, although they have a whole curve of zeros. The multigrid methods we develop are especially designed for structured matrix classes, making heavy use of the associated generating functions. In a previous article [13] , we have extended well-known multigrid methods from the isolated zero case to functions with zero curves. In those methods the whole zero curve is represented on coarser grids. Since this implies that zero curves become larger on coarser levels, the number of levels in our multigrid method is limited. Therefore we propose a different approach in this paper. We split the original problem into a fixed number of coarse grid problems. Corresponding to a generating function with isolated zeros, each of them locally represents one part of the zero curve. We combine this splitting technique with the methods from [13] to construct a faster and more robust multigrid solver