Algebraic Multigrid (AMG)

Build Status

This package lets you solve sparse linear systems using Algebraic Multigrid (AMG). This works especially well for symmetric positive definite matrices.

Usage

Using the CommonSolve interface

This is highest level API. It internally creates the multilevel object and calls the multigrid cycling _solve.

A = poisson(100); 
b = rand(100);
solve(A, b, RugeStubenAMG(), maxiter = 1, abstol = 1e-6)

Multigrid cycling

using AlgebraicMultigrid

A = poisson(1000) # Creates a sample symmetric positive definite sparse matrix
ml = ruge_stuben(A) # Construct a Ruge-Stuben solver
# Multilevel Solver
# -----------------
# Operator Complexity: 1.9859906604402935
# Grid Complexity: 1.99
# No. of Levels: 8
# Coarse Solver: AMG.Pinv()
# Level     Unknowns     NonZeros
# -----     --------     --------
#     1         1000         2998 [50.35%]
#     2          500         1498 [25.16%]
#     3          250          748 [12.56%]
#     4          125          373 [ 6.26%]
#     5           62          184 [ 3.09%]
#     6           31           91 [ 1.53%]
#     7           15           43 [ 0.72%]
#     8            7           19 [ 0.32%]


AlgebraicMultigrid._solve(ml, A * ones(1000)) # should return ones(1000)

As a Preconditioner

You can use AMG as a preconditioner for Krylov methods such as Conjugate Gradients.

import IterativeSolvers: cg
p = aspreconditioner(ml)
c = cg(A, A*ones(1000), Pl = p)

As a preconditioner with LinearSolve.jl

RugeStubenPreconBuilder and SmoothedAggregationPreconBuilder work with the precs API of LinearSolve.jl

A = poisson( (100,100) )
u0= rand(size(A,1))
b=A*u0

prob = LinearProblem(A, b)
strategy = KrylovJL_CG(precs = RugeStubenPreconBuilder())
sol = solve(prob, strategy, atol=1.0e-14)

strategy = KrylovJL_CG(precs = SmoothedAggregationPreconBuilder())
sol = solve(prob, strategy, atol=1.0e-14)

Custom smoothers

To use a custom smoother please dispatch

setup_smoother(config::Smoother, A::AbstractMatrix, symmetry)::S
smooth!(x, smoother::S, b)

Where S denotes the smoothers cache which also must hold the matrix A. smooth! performs relaxation steps updating the current iterate x in-place: x ← x + S⁻¹(b − A·x).

Coarse solver

Users can choose from different coarse solvers.

• AlgebraicMultigrid.LinearSolveWrapper(alg) where alg is any LinearSolve.jl solver (https://docs.sciml.ai/LinearSolve/stable/basics/algorithm_selection/#Algorithm-Categories)
• AlgebraicMultigrid.QRSolver
• AlgebraicMultigrid.Pinv

Features and Roadmap

This package currently supports:

AMG Styles:

• Ruge-Stuben Solver
• Smoothed Aggregation (SA) with handling of user-provided near null spaces

Strength of Connection:

• Classical Strength of Connection
• Symmetric Strength of Connection

Smoothers:

• Gauss Seidel (Symmetric, Forward, Backward)
• Damped Jacobi
• SOR and SSOR

Cycling:

• V, W and F cycles

In the future, this package will support:

1. Other splitting methods (like CLJP)
2. AMLI cycles
3. Root-Node AMG
4. Shared-memory parallelization of relevant internal functions

Acknowledgements

This package has been heavily inspired by the PyAMG project.