# Parallel AMG

**URL:** <https://discourse.julialang.org/t/parallel-amg/88926>\
**Category:** Numerics\
**Created:** [October 18, 2022, 6:59pm UTC](https://discourse.julialang.org/t/parallel-amg/88926 "2022-10-18T18:59:20Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![nvenkov1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nvenkov1/32/43679_2.png) [@nvenkov1](https://discourse.julialang.org/u/nvenkov1)\
**Post date:** [October 18, 2022, 6:59pm UTC](https://discourse.julialang.org/t/parallel-amg/88926/1 "2022-10-18T18:59:20Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [October 19, 2022, 4:48am UTC](https://discourse.julialang.org/t/parallel-amg/88926/2 "2022-10-19T04:48:42Z")

</div>

> **[GitHub - JuliaLinearAlgebra/AlgebraicMultigrid.jl: Algebraic Multigrid in Julia](https://github.com/JuliaLinearAlgebra/AlgebraicMultigrid.jl)**
>
> Algebraic Multigrid in Julia. Contribute to JuliaLinearAlgebra/AlgebraicMultigrid.jl development by creating an account on GitHub.

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

---

<div class="post-metadata">

**Author:** ![nvenkov1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nvenkov1/32/43679_2.png) [@nvenkov1](https://discourse.julialang.org/u/nvenkov1)\
**Post date:** [October 19, 2022, 9:02pm UTC](https://discourse.julialang.org/t/parallel-amg/88926/3 "2022-10-19T21:02:34Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ranjan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ranjan/32/4832_2.png) [@ranjan](https://discourse.julialang.org/u/ranjan)\
**Post date:** [October 19, 2022, 9:14pm UTC](https://discourse.julialang.org/t/parallel-amg/88926/4 "2022-10-19T21:14:13Z")

</div>

Ah that looks like a bug. Filed an issue here: [Inf on preconditioner \ b · Issue #98 · JuliaLinearAlgebra/AlgebraicMultigrid.jl · GitHub](https://github.com/JuliaLinearAlgebra/AlgebraicMultigrid.jl/issues/98). Looking into it

---

<div class="post-metadata">

**Author:** ![ranjan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ranjan/32/4832_2.png) [@ranjan](https://discourse.julialang.org/u/ranjan)\
**Post date:** [October 19, 2022, 10:59pm UTC](https://discourse.julialang.org/t/parallel-amg/88926/5 "2022-10-19T22:59:20Z")

</div>

> [@nvenkov1](#):
>
> 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

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:

```Julia
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

```

---

<div class="post-metadata">

**Author:** ![nvenkov1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nvenkov1/32/43679_2.png) [@nvenkov1](https://discourse.julialang.org/u/nvenkov1)\
**Post date:** [October 20, 2022, 8:45am UTC](https://discourse.julialang.org/t/parallel-amg/88926/6 "2022-10-20T08:45:15Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [October 20, 2022, 9:31am UTC](https://discourse.julialang.org/t/parallel-amg/88926/7 "2022-10-20T09:31:28Z")

</div>

iLU doesn’t require diagonally dominant.

---

<div class="post-metadata">

**Author:** ![ranjan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ranjan/32/4832_2.png) [@ranjan](https://discourse.julialang.org/u/ranjan)\
**Post date:** [October 20, 2022, 2:40pm UTC](https://discourse.julialang.org/t/parallel-amg/88926/8 "2022-10-20T14:40:33Z")

</div>

Preconditioners.jl just calls into AlgebraicMultigrid.jl

---

<div class="post-metadata">

**Author:** ![nvenkov1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nvenkov1/32/43679_2.png) [@nvenkov1](https://discourse.julialang.org/u/nvenkov1)\
**Post date:** [October 20, 2022, 4:28pm UTC](https://discourse.julialang.org/t/parallel-amg/88926/9 "2022-10-20T16:28:26Z")

</div>

Oh. I didn’t know that.