Reducing complexity in parallel algebraic multigrid preconditioners

Algebraic multigrid (AMG) is a very efficient iterative solver and preconditioner for large unstructured sparse linear systems. Traditional coarsening schemes for AMG can, however, lead to computational complexity growth as problem size increases, resulting in increased memory use and execution time...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on matrix analysis and applications 2006, Vol.27 (4), p.1019-1039
Main Authors: DE STERCK, Hans, MEIER YANGS, Ulrike, HEYS, Jeffrey J
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Applied mathematics
Exact sciences and technology
Iterative methods
Laboratories
Mathematics
Methods of scientific computing (including symbolic computation, algebraic computation)
Numerical analysis
Numerical analysis. Scientific computation
Numerical linear algebra
Partial differential equations, boundary value problems
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Algebraic multigrid (AMG) is a very efficient iterative solver and preconditioner for large unstructured sparse linear systems. Traditional coarsening schemes for AMG can, however, lead to computational complexity growth as problem size increases, resulting in increased memory use and execution time, and diminished scalability. Two new parallel AMG coarsening schemes are proposed that are based solely on enforcing a maximum independent set property, resulting in sparser coarse grids. The new coarsening techniques remedy memory and execution time complexity growth for various large three-dimensional (3D) problems. If used within AMG as a preconditioner for Krylov subspace methods, the resulting iterative methods tend to converge fast. This paper discusses complexity issues that can arise in AMG, describes the new coarsening schemes, and examines the performance of the new preconditioners for various large 3D problems.
ISSN:0895-4798
1095-7162
DOI:10.1137/040615729