Efficient Setup Algorithms for Parallel Algebraic Multigrid
David M. Alber · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2007
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.