BoomerAMG: A parallel algebraic multigrid solver and preconditioner

• Published in: Applied numerical mathematics 2002-04, Vol.41 (1), p.155-177
• Main Authors: Henson, Van Emden, Yang, Ulrike Meier
• Format: Article
• Language: English
• Subjects: Algebraic multigrid; Exact sciences and technology; Mathematics; Parallel computing; Sciences and techniques of general use
• ISSN: 0168-9274; 1873-5460
• DOI: 10.1016/S0168-9274(01)00115-5

Driven by the need to solve linear systems arising from problems posed on extremely large, unstructured grids, there has been a recent resurgence of interest in algebraic multigrid (AMG). AMG is attractive in that it holds out the possibility of multigrid-like performance on unstructured grids. The sheer size of many modern physics and simulation problems has led to the development of massively parallel computers, and has sparked much research into developing algorithms for them. Parallelizing AMG is a difficult task, however. While much of the AMG method parallelizes readily, the process of coarse-grid selection, in particular, is fundamentally sequential in nature. We have previously introduced a parallel algorithm [A.J. Cleary, R.D. Falgout, V.E. Henson, J.E. Jones, in: Proceedings of the Fifth International Symposium on Solving Irregularly Structured Problems in Parallel, Springer, New York, 1998] for the selection of coarse-grid points, based on modifications of certain parallel independent set algorithms and the application of heuristics designed to insure the quality of the coarse grids, and shown results from a prototype serial version of the algorithm. In this paper we describe an implementation of a parallel AMG code, using the algorithm of A.J. Cleary, R.D. Falgout, V.E. Henson, J.E. Jones [in: Proceedings of the Fifth International Symposium on Solving Irregularly Structured Problems in Parallel, Springer, New York, 1998] as well as other approaches to parallelizing the coarse-grid selection. We consider three basic coarsening schemes and certain modifications to the basic schemes, designed to address specific performance issues. We present numerical results for a broad range of problem sizes and descriptions, and draw conclusions regarding the efficacy of the method. Finally, we indicate the current directions of the research.