Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Heuristics for the Automatic Construction of Coarse Grids in Multigrid Solvers for Finite Element Matrices

Mark Adams

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-98-994
January 1998

http://www.eecs.berkeley.edu/Pubs/TechRpts/1998/CSD-98-994.pdf

The finite element method (FEM) has proven to be a popular spatial discretization technique in the simulation of complex physical systems in many areas of science and engineering. Implicit solution schemes, used in the time discretization, require the application of the inverse of an operator which is usually linear or linearized; thus, after the FEM discretization, a linear set of discrete equations must be solved. The solution of these equations is a dominate cost of FEM. Direct solvers are easy to use; that is they are relatively invariant to condition number and effective (fast) for small scale problems. But for the solution of large complex systems, iterative methods are very attractive due to their potential O( n) time and space complexity. Multigrid (MG) is a powerful solver, or preconditioner, and is ideally suited for FEM matrices. MG performance, however, is significantly influenced by the quality of the coarse grids; maximal independent sets (MISs) are a useful and popular tool in the automatic construction of these coarse grids on unstructured FE meshes. The inherent flexibility common to all MIS algorithms, allow for the use of heuristics to improve their quality. We will present heuristics and methods to optimize the quality of MISs, and the meshes constructed from them, for use in multigrid solvers for 3D continuum mechanics.


BibTeX citation:

@techreport{Adams:CSD-98-994,
    Author = {Adams, Mark},
    Title = {Heuristics for the Automatic Construction of Coarse Grids in Multigrid Solvers for Finite Element Matrices},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1998},
    Month = {Jan},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1998/5564.html},
    Number = {UCB/CSD-98-994},
    Abstract = {The finite element method (FEM) has proven to be a popular spatial discretization technique in the simulation of complex physical systems in many areas of science and engineering. Implicit solution schemes, used in the time discretization, require the application of the inverse of an operator which is usually linear or linearized; thus, after the FEM discretization, a linear set of discrete equations must be solved. The solution of these equations is a dominate cost of FEM. Direct solvers are easy to use; that is they are relatively invariant to condition number and effective (fast) for small scale problems. But for the solution of large complex systems, iterative methods are very attractive due to their potential <i>O</i>(<i>n</i>) time and space complexity. Multigrid (MG) is a powerful solver, or preconditioner, and is ideally suited for FEM matrices. MG performance, however, is significantly influenced by the quality of the coarse grids; maximal independent sets (MISs) are a useful and popular tool in the automatic construction of these coarse grids on unstructured FE meshes. The inherent flexibility common to all MIS algorithms, allow for the use of heuristics to improve their quality. We will present heuristics and methods to optimize the quality of MISs, and the meshes constructed from them, for use in multigrid solvers for 3D continuum mechanics.}
}

EndNote citation:

%0 Report
%A Adams, Mark
%T Heuristics for the Automatic Construction of Coarse Grids in Multigrid Solvers for Finite Element Matrices
%I EECS Department, University of California, Berkeley
%D 1998
%@ UCB/CSD-98-994
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1998/5564.html
%F Adams:CSD-98-994