Mark Adams

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-99-1036

, 1999

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1036.pdf

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 heuristic to 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 algorithms to optimize the quality of MISs, and the meshes constructed from them, for use in multigrid solvers for unstructured problems in solid mechanics. We also discuss parallel issues of our algorithms, and multigrid solvers in general, and describe a parallel finite element architecture that we have developed to parallelize a state-of-the-art research finite element code in a natural way for the common computer architectures of today. We show that our solver, and parallel finite element architecture, does indeed scale well, with test problems in 3D large deformation elasticity and plasticity, with over 26 million degrees of freedom on a 640 processor Cray T3E (with 55% parallel efficiency), and on 84 IBM 4-way SMP PowerPC nodes.

---

BibTeX citation:

@techreport{Adams:CSD-99-1036,
    Author= {Adams, Mark},
    Title= {Parallel Multigrid Algorithms for Unstructured 3D Large Deformation Elasticity and Plasticity Finite Element Problems},
    Year= {1999},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5398.html},
    Number= {UCB/CSD-99-1036},
    Abstract= {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 heuristic to 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 algorithms to optimize the quality of MISs, and the meshes constructed from them, for use in multigrid solvers for unstructured problems in solid mechanics. We also discuss parallel issues of our algorithms, and multigrid solvers in general, and describe a parallel finite element architecture that we have developed to parallelize a state-of-the-art research finite element code in a natural way for the common computer architectures of today. We show that our solver, and parallel finite element architecture, does indeed scale well, with test problems in 3D large deformation elasticity and plasticity, with over 26 million degrees of freedom on a 640 processor Cray T3E (with 55% parallel efficiency), and on 84 IBM 4-way SMP PowerPC nodes.},
}

EndNote citation:

%0 Report
%A Adams, Mark 
%T Parallel Multigrid Algorithms for Unstructured 3D Large Deformation Elasticity and Plasticity Finite Element Problems
%I EECS Department, University of California, Berkeley
%D 1999
%@ UCB/CSD-99-1036
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5398.html
%F Adams:CSD-99-1036