Efficient Setup Algorithms for Parallel Algebraic Multigrid

Alber, David Michael

Permalink

https://hdl.handle.net/2142/11320 Copy

Description

Title

Efficient Setup Algorithms for Parallel Algebraic Multigrid

Author(s)

Alber, David Michael

Issue Date

2007-05

Keyword(s)

• algorithms
• parallel systems

Abstract

Solving partial differential equations (PDEs) using analytical techniques is intractable for all but the simplest problems. Many computational approaches to approximate solutions to PDEs yield large systems of linear equations. Algorithms known as linear solvers then compute an approximate solution to the linear system. Multigrid methods are one class of linear solver and find an approximate solution to a linear system through two complementary processes: relaxation and coarse-grid correction. Relaxation cheaply annihilates portions of error from the approximate solution, while coarse-grid correction constructs a lower dimensional problem to remove error remaining after relaxation. In algebraic multigrid (AMG), the lower dimensional space is constructed by coarse-grid selection algorithms. In this thesis, an introduction and study of independent set-based parallel coarse-grid selection algorithms is presented in detail, following a review of algebraic multigrid. The behavior of the Cleary-Luby-Jones-Plassmann (CLJP) algorithm is analyzed and modifications to the initialization phase of CLJP are recommended, resulting in the CLJP in Color (CLJP-c) algorithm, which achieves large performance gains over CLJP for problems on uniform grids. CLJP-c is then extended to the Parallel Modified Independent Set (PMIS) coarse-grid selection algorithm producing the PMIS-c1 and PMIS-c2 algorithms. Experimental results are provided for six problems run with a large collection of independent set-based coarsening algorithms. The experimental results motivate the design of new coarsening algorithms to improve the performance of coarse-grid selection itself. A new algorithm labeled Bucket Sorted Independent Sets (BSIS) is developed and contributes two major advances. First, the cost of selecting independent sets while coarsening is substantially less expensive, with experiments demonstrating 23% savings over CLJP-c. Second, theory is developed proving that all generalized forms of the coarsening algorithms studied in this thesis using the same selection and update parameters choose identical coarse grids, given the same initial weights. The theory is powerful because it provides insight and enables the development of more efficient algorithms without affecting convergence properties.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11320

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections