BoomerAMG

BoomerAMG is a parallel implementation of the algebraic multigrid method [RuSt1987]. It can be used both as a solver or as a preconditioner. The user can choose between various different parallel coarsening techniques, interpolation and relaxation schemes. The default settings for CPUs, HMIS (coarsening 8) combined with a distance-two interpolation (6) truncated to 4 or 5 elements per row, should work fairly well for two- and three-dimensional diffusion problems. Additional reduction in complexity and increased scalability can often be achieved using one or two levels of aggressive coarsening.

Parameter Options

Various BoomerAMG functions and options are mentioned below. However, for a complete listing and description of all available functions, see the reference manual.

BoomerAMG’s Create function differs from the synopsis in that it has only one parameter HYPRE_BoomerAMGCreate(HYPRE_Solver *solver). It uses the communicator of the matrix A.

Coarsening Options

Coarsening can be set by the user using the function HYPRE_BoomerAMGSetCoarsenType. A detailed description of various coarsening techniques can be found in [HeYa2002], [Yang2005].

Various coarsening techniques are available:

  • the Cleary-Luby-Jones-Plassman (CLJP) coarsening,

  • parallel versions of the classical RS coarsening described in [HeYa2002].

  • the Falgout coarsening which is a combination of CLJP and the classical RS coarsening algorithm,

  • CGC and CGC-E coarsenings [GrMS2006a], [GrMS2006b],

  • PMIS and HMIS coarsening algorithms which lead to coarsenings with lower complexities [DeYH2004] as well as

  • aggressive coarsening, which can be applied to any of the coarsening techniques mentioned above a nd thus achieving much lower complexities and lower memory use [Stue1999].

To use aggressive coarsening users have to set the number of levels to which they want to apply aggressive coarsening (starting with the finest level) via HYPRE_BoomerAMGSetAggNumLevels. Since aggressive coarsening requires long range interpolation, multipass interpolation is always used on levels with aggressive coarsening, unless the user specifies another long-range interpolation suitable for aggressive coarsening via HYPRE_BoomerAMGSetAggInterpType..

Note that the default coarsening for CPUs is HMIS, for GPUs PMIS [DeYH2004].

Interpolation Options

Various interpolation techniques can be set using HYPRE_BoomerAMGSetInterpType:

  • the “classical” interpolation (0) as defined in [RuSt1987],

  • direct interpolation (3) [Stue1999],

  • standard interpolation (8) [Stue1999],

  • an extended “classical” interpolation, which is a long range interpolation and is recommended to be used with PMIS and HMIS coarsening for harder problems (6) [DFNY2008],

  • distance-two interpolation based on matrix operations (17) [LiSY2021],

  • multipass interpolation (4) [Stue1999],

  • two-stage interpolation [Yang2010],

  • Jacobi interpolation [Stue1999],

  • the “classical” interpolation modified for hyperbolic PDEs (2).

Jacobi interpolation is only used to improve certain interpolation operators and can be used with HYPRE_BoomerAMGSetPostInterpType. Since some of the interpolation operators might generate large stencils, it is often possible and recommended to control complexity and truncate the interpolation operators using HYPRE_BoomerAMGSetTruncFactor and/or HYPRE_BoomerAMGSetPMaxElmts, or HYPRE_BoomerAMGSetJacobiTruncTheshold (for Jacobi interpolation only).

Note that the default interpolation is extended+i interpolation [DFNY2008] truncated to 4 elements per row, for CPUs, and a version of this interpolation based on matrix operations for GPUs [LiSY2021].

Non-Galerkin Options

In order to reduce communication, there is a non-Galerkin coarse grid sparsification option available [FaSc2014]. This option can be used by itself or with existing strategies to reduce communication such as aggressive coarsening and HMIS coarsening. To use, call HYPRE_BoomerAMGSetNonGalerkTol, which gives BoomerAMG a list of level specific non-Galerkin drop tolerances. It is common to drop more aggressively on coarser levels. A common choice of drop-tolerances is \([0.0, 0.01, 0.05]\) where the value of 0.0 will skip the non-Galerkin process on the first coarse level (level 1), use a drop-tolerance of 0.01 on the second coarse level (level 2) and then use 0.05 on all subsequent coarse levels. While still experimental, this capability has significantly improved performance on a variety of problems. See the ij driver for an example usage and the reference manual for more details.

Smoother Options

A good overview of parallel smoothers and their properties can be found in [BFKY2011]. Various of the described relaxation techniques are available:

  • weighted Jacobi relaxation (0),

  • a hybrid Gauss-Seidel / Jacobi relaxation scheme (3 4),

  • a symmetric hybrid Gauss-Seidel / Jacobi relaxation scheme (6),

  • l1-Gauss-Seidel or Jacobi (13 14 18 8),

  • Chebyshev smoothers (16),

  • two-stage Gauss-Seidel smoothers (11 12) [BKRHSMTY2021],

  • hybrid block and Schwarz smoothers [Yang2004],

  • Incomplete LU factorization, see ILU as Smoother for BoomerAMG.

  • Factorized Sparse Approximate Inverse (FSAI), see FSAI as Smoother to BoomerAMG.

Point relaxation schemes can be set using HYPRE_BoomerAMGSetRelaxType or, if one wants to specifically set the up cycle, down cycle or the coarsest grid, with HYPRE_BoomerAMGSetCycleRelaxType. To use the more complicated smoothers, e.g. block, Schwarz, ILU smoothers, it is necessary to use HYPRE_BoomerAMGSetSmoothType and HYPRE_BoomerAMGSetSmoothNumLevels. There are further parameter choices for the individual smoothers, which are described in the reference manual. The default relaxation type is l1-Gauss-Seidel, using a forward solve on the down cycle and a backward solve on the up-cycle, to keep symmetry. Note that if BoomerAMG is used as a preconditioner for conjugate gradient, it is necessary to use a symmetric smoother. Other symmetric options are weighted Jacobi or hybrid symmetric Gauss-Seidel.

AMG for systems of PDEs

If the users wants to solve systems of PDEs and can provide information on which variables belong to which function, BoomerAMG’s systems AMG version can also be used. Functions that enable the user to access the systems AMG version are HYPRE_BoomerAMGSetNumFunctions, HYPRE_BoomerAMGSetDofFunc and HYPRE_BoomerAMGSetNodal.

There are basically two approaches to deal with matrices derived from systems of PDEs. The unknown-based approach (which is the default) treats variables corresponding to the same unknown or function separately, i.e., when coarsening or generating interpolation, connections between variables associated with different unknowns are ignored. This can work well for weakly coupled PDEs, but will be problematic for strongly coupled PDEs. For such problems, we recommend to use hypre’s multigrid reduction (MGR) solver. The second approach, called the nodal approach, considers all unknowns at a physical grid point together such that coarsening, interpolation and relaxation occur in a point-wise fashion. It is possible and sometimes prefered to combine nodal coarsening with unknown-based interpolation. For this case, HYPRE_BoomerAMGSetNodal should be set > 1. For details see the reference manual.

If the user can provide the near null-space vectors, such as the rigid body modes for linear elasticity problems, an interpolation is available that will incorporate these vectors with HYPRE_BoomerAMGSetInterpVectors and HYPRE_BoomerAMGSetInterpVecVariant. This can lead to improved convergence and scalability [BaKY2010].

Special AMG Cycles

The default cycle is a V(1,1)-cycle, however it is possible to change the number of sweeps of the up- and down-cycle as well as the coare grid. One can also choose a W-cycle, however for parallel processing this is not recommended, since it is not scalable.

BoomerAMG also provides an additive V(1,1)-cycle as well as a mult-additive V(1,1)-cycle and a simplified versioni [VaYa2014]. The additive variants can only be used with weighted Jacobi or l1-Jacobi smoothing.

GPU-supported Options

In general, CUDA unified memory is required for running BoomerAMG solvers on GPUs. However, hypre can also be built without --enable-unified-memory if all the selected parameters have GPU-support. The currently available GPU-supported BoomerAMG options include:

  • Coarsening: PMIS (8)

  • Interpolation: direct (3), BAMG-direct (15), extended (14), extended+i (6) and extended+e (18)

  • Aggressive coarsening

  • Second-stage interpolation with aggressive coarsening: extended (5) and extended+e (7)

  • Smoother: Jacobi (7), l1-Jacobi (18), hybrid Gauss Seidel/SSOR (3 4 6), two-stage Gauss-Seidel (11,12) [BKRHSMTY2021], and Chebyshev (16)

  • Relaxation order can be 0, lexicographic order, or C/F for (7) and (18)

Memory locations and execution policies

Hypre provides two user-level memory locations, HYPRE_MEMORY_HOST and HYPRE_MEMORY_DEVICE, where HYPRE_MEMORY_HOST is always the CPU memory while HYPRE_MEMORY_DEVICE can be mapped to different memory spaces based on the configure options of hypre. When built with --with-cuda, --with-hip, --with-sycl, or --with-device-openmp, HYPRE_MEMORY_DEVICE is the GPU device memory, and when built additionally with --enable-unified-memory, it is the GPU unified memory (UM). For a non-GPU build, HYPRE_MEMORY_DEVICE is also mapped to the CPU memory. The default memory location of hypre’s matrix and vector objects is HYPRE_MEMORY_DEVICE, which can be changed at runtime by HYPRE_SetMemoryLocation(...).

The execution policies define the platform of running computations based on the memory locations of participating objects. The default policy is HYPRE_EXEC_HOST, i.e., executing on the host if the objects are accessible from the host. It can be adjusted by HYPRE_SetExecutionPolicy(...). Clearly, this policy only affects objects in UM, since UM is accessible from both CPUs and GPUs.

A sample code of setting up IJ matrix \(A\) and solve \(Ax=b\) using AMG-preconditioned CG on GPUs is shown below.

cudaSetDevice(device_id); /* GPU binding */
...
HYPRE_Initialize(); /* must be the first HYPRE function call */
...
/* AMG in GPU memory (default) */
HYPRE_SetMemoryLocation(HYPRE_MEMORY_DEVICE);
/* setup AMG on GPUs */
HYPRE_SetExecutionPolicy(HYPRE_EXEC_DEVICE);
/* use hypre's SpGEMM instead of vendor implementation */
HYPRE_SetSpGemmUseVendor(FALSE);
/* use GPU RNG */
HYPRE_SetUseGpuRand(TRUE);
if (useHypreGpuMemPool)
{
   /* use hypre's GPU memory pool */
   HYPRE_SetGPUMemoryPoolSize(bin_growth, min_bin, max_bin, max_bytes);
}
else if (useUmpireGpuMemPool)
{
   /* or use Umpire GPU memory pool */
   HYPRE_SetUmpireUMPoolName("HYPRE_UM_POOL_TEST");
   HYPRE_SetUmpireDevicePoolName("HYPRE_DEVICE_POOL_TEST");
}
...
/* setup IJ matrix A */
HYPRE_IJMatrixCreate(comm, first_row, last_row, first_col, last_col, &ij_A);
HYPRE_IJMatrixSetObjectType(ij_A, HYPRE_PARCSR);
/* GPU pointers; efficient in large chunks */
HYPRE_IJMatrixAddToValues(ij_A, num_rows, num_cols, rows, cols, data);
HYPRE_IJMatrixAssemble(ij_A);
HYPRE_IJMatrixGetObject(ij_A, (void **) &parcsr_A);
...
/* setup AMG */
HYPRE_ParCSRPCGCreate(comm, &solver);
HYPRE_BoomerAMGCreate(&precon);
HYPRE_BoomerAMGSetRelaxType(precon, rlx_type); /* 3, 4, 6, 7, 18, 11, 12 */
HYPRE_BoomerAMGSetRelaxOrder(precon, FALSE); /* must be false */
HYPRE_BoomerAMGSetCoarsenType(precon, coarsen_type); /* 8 */
HYPRE_BoomerAMGSetInterpType(precon, interp_type); /* 3, 15, 6, 14, 18 */
HYPRE_BoomerAMGSetAggNumLevels(precon, agg_num_levels);
HYPRE_BoomerAMGSetAggInterpType(precon, agg_interp_type); /* 5 or 7 */
HYPRE_BoomerAMGSetKeepTranspose(precon, TRUE); /* keep transpose to avoid SpMTV */
HYPRE_BoomerAMGSetRAP2(precon, FALSE); /* RAP in two multiplications
                                          (default: FALSE) */
HYPRE_ParCSRPCGSetPrecond(solver, HYPRE_BoomerAMGSolve, HYPRE_BoomerAMGSetup,
                          precon);
HYPRE_PCGSetup(solver, parcsr_A, b, x);
...
/* solve */
HYPRE_PCGSolve(solver, parcsr_A, b, x);
...
HYPRE_Finalize(); /* must be the last HYPRE function call */

HYPRE_Initialize() must be called and precede all the other HYPRE_ functions, and HYPRE_Finalize() must be called before exiting.

Miscellaneous

For best performance, it might be necessary to set certain parameters, which will affect both coarsening and interpolation. One important parameter is the strong threshold, which can be set using the function HYPRE_BoomerAMGSetStrongThreshold. The default value is 0.25, which appears to be a good choice for diffusion problems. The choice of the strength threshold is problem dependent. For example, elasticity problems often require a larger strength threshold.