Heuristics for the Automatic Construction of Coarse Grids in Multigrid Solvers for Finite Element Problems in Solid Mechanics

Mark Adams
Department of Civil Engineering
University of California Berkeley
Berkeley, CA 94720


Multigrid is a popular solution method for the set of linear algebraic equations that arise from PDEs discretized with the finite element method. The application of multigrid to unstructured grid problems, however, is not well developed. We discuss a method that uses many of the same techniques as the finite element method itself, to apply standard multigrid algorithms to unstructured finite element problems. We use maximal independent sets (MISs), like many "algebraic" multigrid methods, as a heuristicto automatically coarsen unstructured grids. The inherent flexibility in the selection of an MIS allows for the use of heuristics to improve their effectiveness for a multigrid solver. We present heuristics and algorithmsto optimize the quality of MISs, and the meshes constructed from them, for use in multigrid solvers for unstructured problems in solid mechanics. We present numerical results that demonstrate the effectiveness of the our methods on several model problems in linear elasticity.

Key words: maximal independentsets, multigrid, unstructured meshes, parallel solvers