Volume 2, pp. 171-182, 1994.

Domain decomposition and multigrid algorithms for elliptic problems on unstructured meshes

Tony F. Chan and Barry F. Smith


Multigrid and domain decomposition methods have proven to be versatile methods for the iterative solution of linear and nonlinear systems of equations arising from the discretization of partial differential equations. The efficiency of these methods derives from the use of a grid hierarchy. In some applications to problems on unstructured grids, however, no natural multilevel structure of the grid is available and thus must be generated as part of the solution procedure. In this paper, we consider the problem of generating a multilevel grid hierarchy when only a fine, unstructured grid is given. We restrict attention to problems in two dimensions. Our techniques generate a sequence of coarser grids by first forming a maximal independent set of the graph of the grid or its dual and then applying a Cavendish type algorithm to form the coarser triangulation. Iterates on the different levels are combined using standard interpolation and restriction operators. Numerical tests indicate that convergence using this approach can be as fast as standard multigrid and domain decomposition methods on a structured mesh.

Full Text (PDF) [920 KB]

Key words

domain decomposition, grid refinement, mulitigrid, numerical partial differential equations.

AMS subject classifications

< Back