Parallel AMG

Specific Domains Numerics
1

Has anyone ever started working on a parallel implementation of algebraic multigrid solvers and preconditioners?

2

AlgebraicMultigrid.jl has GPU support, but it could be improved.

3

Good to know, thank you. Although, it does not seem to work. The following returns a vector of Inf values with v0.5.1:

using LinearAlgebra: Tridiagonal
using SparseArrays: sparse
using AlgebraicMultigrid
n = 10_000
A = Tridiagonal(rand(n-1), rand(n), rand(n-1))
A = A + A’
ml = ruge_stuben(sparse(A))
M = aspreconditioner(ml)
b = rand(n)
M \ b

4

Ah that looks like a bug. Filed an issue here: Inf on preconditioner \ b · Issue #98 · JuliaLinearAlgebra/AlgebraicMultigrid.jl · GitHub. Looking into it

5

This is failing at the Gauss Seidel relaxation step. Gauss Seidel is guaranteed to converge only for diagonally dominant matrices, so this makes sense. So I would recommend trying it like this:

using LinearAlgebra: Tridiagonal
using SparseArrays: sparse
using AlgebraicMultigrid
n = 10_000
A = Tridiagonal(rand(n-1), 100*rand(n), rand(n-1))
A = A + A'
ml = ruge_stuben(sparse(A))
M = aspreconditioner(ml)
b = rand(n)
M \ b
6

You are right. The smoothed aggregation-based AMG preconditioner of the Preconditioners.jl package also fails with a LAPACK error for this array. Do all smoothers require diagonal dominance? Is there no way to design an AMG solver or preconditioner for a non-diagonally dominant matrix?

7

iLU doesn’t require diagonally dominant.

1 Like
8

Preconditioners.jl just calls into AlgebraicMultigrid.jl

9

Oh. I didn’t know that.