IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Efficient Setup Algorithms for Parallel Algebraic Multigrid

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/11320

Files in this item

File Description Format
PDF Efficient Setup ... el Algebraic Multigrid.pdf (4MB) (no description provided) PDF
Title: Efficient Setup Algorithms for Parallel Algebraic Multigrid
Author(s): Alber, David Michael
Subject(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.
Issue Date: 2007-05
Genre: Technical Report
Type: Text
URI: http://hdl.handle.net/2142/11320
Other Identifier(s): UIUCDCS-R-2007-2829
Rights 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).
Date Available in IDEALS: 2009-04-22
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 158
  • Downloads this Month: 3
  • Downloads Today: 0

Browse

My Account

Information

Access Key