Mark Francis Adams
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-99-1033
January 1999
http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1033.pdf
The finite element method has grown, in the past 40 years, to be a popular method for the simulation of physical systems in science and engineering. The finite element method is used in a wide array of industries. In fact just about any enterprise that makes a physical product can, and probably does, use finite element technology. The success of the finite element method is due in large part to its ability to allow the use of accurate formulation of partial differential equations (PDEs), on arbitrarily general physical domains with complex boundary conditions. Additionally, the rapid growth in the computational power available in today's computers -- for an ever more affordable price -- has made finite element technology more accessible to a wider variety of industries and academic disciplines.
As computational resources allow people to produce ever more accurate simulation of their systems -- allowing for the more efficient design and safety testing of everything from automobiles to nuclear weapons to artificial knee joints -- all aspects of the finite element simulation process are stressed. The largest bottleneck in the growth in the scale of finite element applications is the linear equation solver used in implicit time integration schemes. This is due to the fact that the direct solution methods -- popular in the finite element community as they are efficient, easy to use, and relatively unaffected by the underlying PDE and discretization -- do not scale well with increasing problem size.
The scale of problems that are now becoming feasible demand that iterative methods be used. The performance issues of iterative methods is very different from those of direct methods, as their performance is highly sensitive to the underlying PDE and discretization; the construction of robust iterative methods for finite element matrices is a hard problem which is currently a very active area of research. We discuss the iterative methods commonly used today, and show that they can all be characterized as methods that solve problems efficiently by projecting the solution to a series of subspaces. The goal of iterative method design, and indeed of finite element method design, is to select a series of subspaces that solves problems "optimally"; solvers try to minimize solution costs and finite element formulations try to optimize accuracy of the solution. The subspaces used in multigrid methods are highly effective in minimizing solution costs -- particularly on large problems. Multigrid is known to be the most effective solution method for some discretized PDEs, however its effective use on unstructured finite element meshes is an open problem, and constitutes the theme of this study.
The main contribution of this dissertation is the algorithmic development and experimental analysis of robust and scalable techniques for the solution of the sparse, ill-conditioned matrices that arise from finite element simulation in 3D continuum mechanics. We show that our multigrid formulations are effective in the linear solution of systems with large jumps in material coefficients, for problems with realistic mesh configuration and geometries (including poorly proportioned elements), and for problems with poor "geometric" conditioning as is commonplace in structural engineering. We show that the these methods can be used effectively within nonlinear simulations via Newton's method. We solve problems with more than sixteen million degrees of freedom and parallel solver efficiency of about 60% on 512 processors of a Cray T3E. We also show that our methods can be adapted and extended to the indefinite matrices that arise in the simulation of problems with constraints, namely contact problems, formulated with Lagrange multiplier.
BibTeX citation:
@techreport{Adams:CSD-99-1033,
Author = {Adams, Mark Francis},
Title = {Multigrid Equation Solvers for Large Scale Nonlinear Finite Element Simulations},
Institution = {EECS Department, University of California, Berkeley},
Year = {1999},
Month = {Jan},
URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5430.html},
Number = {UCB/CSD-99-1033},
Abstract = {The finite element method has grown, in the past 40 years, to be a popular method for the simulation of physical systems in science and engineering. The finite element method is used in a wide array of industries. In fact just about any enterprise that makes a physical product can, and probably does, use finite element technology. The success of the finite element method is due in large part to its ability to allow the use of accurate formulation of partial differential equations (PDEs), on arbitrarily general physical domains with complex boundary conditions. Additionally, the rapid growth in the computational power available in today's computers -- for an ever more affordable price -- has made finite element technology more accessible to a wider variety of industries and academic disciplines. <p>As computational resources allow people to produce ever more accurate simulation of their systems -- allowing for the more efficient design and safety testing of everything from automobiles to nuclear weapons to artificial knee joints -- all aspects of the finite element simulation process are stressed. The largest bottleneck in the growth in the scale of finite element applications is the linear equation solver used in implicit time integration schemes. This is due to the fact that the direct solution methods -- popular in the finite element community as they are efficient, easy to use, and relatively unaffected by the underlying PDE and discretization -- do not scale well with increasing problem size. <p>The scale of problems that are now becoming feasible demand that iterative methods be used. The performance issues of iterative methods is very different from those of direct methods, as their performance is highly sensitive to the underlying PDE and discretization; the construction of robust iterative methods for finite element matrices is a hard problem which is currently a very active area of research. We discuss the iterative methods commonly used today, and show that they can all be characterized as methods that solve problems efficiently by projecting the solution to a series of subspaces. The goal of iterative method design, and indeed of finite element method design, is to select a series of subspaces that solves problems "optimally"; solvers try to minimize solution costs and finite element formulations try to optimize accuracy of the solution. The subspaces used in multigrid methods are highly effective in minimizing solution costs -- particularly on large problems. Multigrid is known to be the most effective solution method for some discretized PDEs, however its effective use on unstructured finite element meshes is an open problem, and constitutes the theme of this study. <p>The main contribution of this dissertation is the algorithmic development and experimental analysis of robust and scalable techniques for the solution of the sparse, ill-conditioned matrices that arise from finite element simulation in 3D continuum mechanics. We show that our multigrid formulations are effective in the linear solution of systems with large jumps in material coefficients, for problems with realistic mesh configuration and geometries (including poorly proportioned elements), and for problems with poor "geometric" conditioning as is commonplace in structural engineering. We show that the these methods can be used effectively within nonlinear simulations via Newton's method. We solve problems with more than sixteen million degrees of freedom and parallel solver efficiency of about 60% on 512 processors of a Cray T3E. We also show that our methods can be adapted and extended to the indefinite matrices that arise in the simulation of problems with constraints, namely contact problems, formulated with Lagrange multiplier.}
}
EndNote citation:
%0 Report %A Adams, Mark Francis %T Multigrid Equation Solvers for Large Scale Nonlinear Finite Element Simulations %I EECS Department, University of California, Berkeley %D 1999 %@ UCB/CSD-99-1033 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5430.html %F Adams:CSD-99-1033