a Parallel Algebraic Multigrid Solver; Implementation and Enhancements

Center for Applied Scientific Computing

Lawrence Livermore National Laboratory

Box 808, L-560

Livermore CA 94551

Abstract

Modern scientists must solve increasingly large linear systems, with
hundreds of millions, or even billions, of unknowns. This has
necessitated the use of massively parallel computers, which has in
turn led to the investigation of scalable linear solvers, such as
multigrid. For unstructured grid problems, an attractive choice is
algebraic multigrid (AMG). We have implemented
** BoomerAMG,** an AMG code for massively parallel computers
with distributed memory.

Much of the classical AMG algorithm can be parallelized in a
straightforward fashion; for example, the entire "solve" phase can be
implemented using parallel matvec or matvec-like operations. However,
the classical coarse-grid selection algorithm is highly
sequential. ** BoomerAMG** provides the choice of several
parallel coarsening strategies: the "CLJP" method, based on a parallel
algorithm by Luby, Jones and Plassmann for finding maximal independent
sets; the "RS" approach, a parallel variant of the classical algorithm
in which the sequential algorithm is performed on each processor and
several options are available to treat the points near the processor
boundaries; and finally, the "Falgout" algorithm, a combination of the
two approaches above.

** BoomerAMG** also offers two choices for the parallel
smoother: the first is weighted Jacobi while the alternative is a
"chaotic" Gauss-Seidel relaxation. This latter method uses
Gauss-Seidel locally, within each processor, but updates the values on
the processor boundary only after each sweep over the processor
domain.

We describe the code and present test results and timings for a variety of test problems. We compare the performance of the coarsening strategies for various settings of the input parameters. We describe some alterations to the basic algorithm that improve convergence factors (or prevent divergence) for certain test problems. We examine the question of how to define the "strong connections" and choose the "strength threshold" for the coarsening algorithms. Results are given showing the influence of the strength threshold on convergence and computation time.

Finally, we indicate the current direction our research is taking and
describe our plans for the future of *BoomerAMG.*

*This work was performed under the auspices of the U.S. Department of
Energy by Lawrence Livermore National Laboratory under contract number
W-7405-Eg-48.