Prometheus Project Overview

Prometheus-1.x: Parallel Multigrid Solver Library for Unstructured Finite Element Problems

Mark Adams   (ma2325@columbia.edu)

Computer Science Division, at U.C. Berkeley


Prometheus is a highly parallel multigrid solver for the set of linear algebraic equations Ax=b that arise from three dimensional finite element discretizations of PDEs.  Prometheus has been used extensively for our research on Cray T3Es and IBM PowerPC clusters to solve large deformation elasticity and plasticity problems on unstructured first order hexahedral and tetrahedral grids with over 39 million degrees of freedom, large jumps in material coefficients, and nearly incompressible materials.  We attain about 60% parallel efficiency and 20 Gflops on 960 processors on an IBM PowerPC cluster.  We have also ported Prometheus to the SGI Origin/2000, the DEC alpha, and Linux PC clusters.  Prometheus is implemented in C++ and callable from C, C++ and FORTRAN, and is built on PETSc and ParMetis.  (Note, using the correct versions of PETSc and ParMetis is very important - we will try to keep Prometheus up to date with the current versions of these libraries).

Prometheus uses multigrid to precondition Krylov subspace methods to solve for x in nonsingular matrix equations of the form Ax=b.  This work was the focus of my Ph.D. dissertation; see my home page for literature on the algorithms, construction, and capabilities of the code, and  here for a brief graphic overview and numerical results.

Multigrid is known to be a highly effective method for solving the linear algebraic equations the arise from discretized analysis of partial differential equations (PDEs).  Multigrid uses of a series of coarse grid approximations of the "fine" grid problem.  Multigrid also uses restriction operators (R), which map residuals from fine grids to coarse grids, prolongation operators (P,  usually implemented with RT),  which map solutions from coarse grids to fine grids, and coarse grid operators Ai on each grid i.  We use the "algebraic" construction of the coarse grid operators by a Galerkin method (Ai+1 := RAiP).

The Prometheus solver library has two fully parallelized unstructured multigrid methods implemented, the first (which we refer to as Prometheus as) automatically constructs  the coarse grids using an algorithm based on Maximal Independent Sets and Delaunay Tessellation; constructs the restriction operators R by using linear finite element shape functions on the coarse grid;  uses P=RT as prolongation operators.   Prometheus also contains an algebraic multigrid algorithm to construct the restriction operators that we call Atlas.

We have recently add a new "algebraic" multigrid method ("smoothed aggregation", by Vanek, Mandel, and Brezina) in a component called Atlas.  Like Prometheus, Atlas is fully parallelized and shares the parallel multigrid substraight Epimetheus (Built on PETSc) and provides similar, and sometimes better, performance as Prometheus and is simpler and perhaps more robust algorithm.  Check my home page for an upcoming paper comparing our two multigrid methods.

The Prometheus library is designed to fit into existing finite element packages as easily as possible and still provide an effective solver for challenging large scale applications.   Prometheus requires that the user provide the finite element mesh - for the fine grid only - in parallel (as well as the matrix A and right hand side b).  Prometheus also provides parallel algebraic multigrid support (the matrix triple product and simplified interface to PETSc).  Prometheus constructs the coarse grid operators and PETSc solver objects and provides a simple user interface to solve linear equations Ax=b for x.

The Prometheus library is in the early stages of development.   We use, and have tested, Prometheus extensively in our research but it has not been used by other people and is thus not a mature library product at this point.  We are interested in working with users, in need of highly scalable solvers, who are willing to work with us so as to make Prometheus more robust, useful, and easy to use for the greater research and industrial FE community.
 

  • This work is supported by the Department of Energy.
  • 1 June 2001