search

GraphBLAS / LAGraph

This is a library plus a test harness for collecting algorithms that use the GraphBLAS. For test coverage reports, see https://graphblas.org/LAGraph/ . Documentation: https://lagraph.readthedocs.org
Other
223 stars 59 forks source link

Algebraic Multigrid Solver implemented in GraphBLAS language? #131

Open learning-chip opened 2 years ago

learning-chip commented 2 years ago

Just notice this nice community effort on GraphBLAS-based algorithms.

I am curious if there are any attempts & interests on translating a complete AMG solver to GraphBLAS language? Some potential benefits I can think of:

  1. Many of AMG coarsening schemes are based on variants of maximal independent set, such as the PMIS scheme in PyAMG and Hypre. All existing implementations are vertex-based. Switching to a linear-algebra (GraphBLAS) based view might improve parallel efficiency and reduce code complexity. Since Luby's parallel MIS algorithm is already implemented GraphBLAS, as well as distance-2 MIS, adapting them for the AMG coarsening variants should be doable (although might require some mental struggling for certain AMG variants)
  2. The rest of AMG procedure mostly contains SpMV (restriction R*x, prolongation P*x) and SpGEMM (garlekin product R*A*P) -- such operations are commonly used and highly optimized in GraphBLAS. The solver expressed in this way can be ported to multi-threaded, GPU, or distributed environment depending on the GraphBLAS backend used, without having to rewrite the algorithm-level code.

I searched on the web, but did not find any work in such direction. Does anyone know any attempts on this? Or there are some instrinsic mathematical/software difficulties?

tgmattso commented 2 years ago

I am not aware of anyone attempting to implement an AMG solver in the GraphBLAS. It would sure be interesting to do so.

--Tim

From: Learning Chip @.> Reply-To: GraphBLAS/LAGraph @.> Date: Wednesday, June 22, 2022 at 8:43 PM To: GraphBLAS/LAGraph @.> Cc: Subscribed @.> Subject: [GraphBLAS/LAGraph] Algebraic Multigrid Solver implemented in GraphBLAS language? (Issue #131)

Just notice this nice community effort on GraphBLAS-based algorithms.

I am curious if there are any attempts & interests on translating a complete AMG solverhttps://en.wikipedia.org/wiki/Multigrid_method#Algebraic_multigrid_(AMG) to GraphBLAS language? Some potential benefits I can think of:

  1. Many of AMG coarsening schemeshttps://onlinelibrary.wiley.com/doi/abs/10.1002/nla.541 are based on variants of maximal independent set, such as the PMIS scheme in PyAMGhttps://github.com/pyamg/pyamg/blob/main/pyamg/classical/split.py and Hyprehttps://hypre.readthedocs.io/en/latest/solvers-boomeramg.html#coarsening-options. All existing implementations are vertex-based. Switching to a linear-algebra (GraphBLAS) based view might improve parallel efficiency and reduce code complexity. Since Luby's parallel MIS algorithm is already implemented GraphBLAShttps://github.com/GraphBLAS/LAGraph/blob/31Dec2021/experimental/algorithm/LAGraph_MaximalIndependentSet.c, as well as distance-2 MIShttps://epubs.siam.org/doi/abs/10.1137/15M104253X, adapting them for the AMG coarsening variants should be doable (although might require some mental struggling for certain AMG variants)
  2. The rest of AMG procedure mostly contains SpMV (restriction Rx, prolongation Px) and SpGEMM (garlekin product RAP) -- such operations are commonly used and highly optimized in GraphBLAS. The solver expressed in this way can be ported to multi-threaded, GPU, or distributed environment depending on the GraphBLAS backend used, without having to rewrite the algorithm-level code.

I searched on the web, but did not find any work in such direction. Does anyone know any attempts on this? Or there are some instrinsic mathematical/software difficulties?

— Reply to this email directly, view it on GitHubhttps://github.com/GraphBLAS/LAGraph/issues/131, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AATVME6PQW6WXAGLORCR5PDVQPMOHANCNFSM5ZSZHTOQ. You are receiving this because you are subscribed to this thread.Message ID: @.***>

DrTimothyAldenDavis commented 2 years ago

Thanks for the note. I'm definitely interested, and have a few efforts towards the algorithms it would need.

We do have MIS (via Luby's method) already in LAGraph. I have a draft code not yet in LAGraph that does a coarsening and node-matching, but it's a method that wouldn't be well suited for AMG. I plan to have one of my undergrad honor students to tackle a maximal node-matching method (similar to MIS), to match pairs of nodes. I think that is what AMG needs? I'm not an AMG expert however. I don't think there are any fundamental roadblocks to any of these methods. It should be possible to write a high-performance AMG for LAGraph+GraphBLAS.

learning-chip commented 2 years ago

I plan to have one of my undergrad honor students to tackle a maximal node-matching method (similar to MIS), to match pairs of nodes. I think that is what AMG needs?

AMG has two major families: 1) Aggregation-based AMG more relies on node matching (merging nearby nodes into one), as adopted by the AGMG package; 2) Classical AMG more relies on MIS-like coarsening, as adopted by Hypre-BoomerAMG.

It is not a standard MIS though. The matrix A is first reduced to a strength-of-connection graph, by dropping small off-diagonals ("weak connections"). Then a variant of MIS is applied to the reduced graph, with certain constraints to ensure interpolation accuracy. The most classic constraint (ref paper Reducing Complexity in Parallel Algebraic Multigrid Preconditioners) is:

H1: For each point j that strongly influences an F-point i, j is either a C-point, or strongly depends on a C-point k that also strongly influences i. H2: The set of C-points needs to form a maximal independent set in the reduced graph of the matrix (with only strong connections retained in the graph).

Of course the constraints can be relaxed, leading to many different variants of AMG coarsening schemes. It remains a research question on how to translate those coarsening scheme (not a standard MIS) to GraphBLAS language.

There are also advanced variants based on matching/aggregation. A maximal node-matching implemention in GraphBLAS would definitely serve as a useful starting point, but more work needs to be done to express the actual matching scheme used by aggregation-type AMG.

After coarsening (i.e. get the sparse pattern of the restriction operator R), AMG also needs an interpolation scheme (i.e. fill-in the non-zero values of the restriction operator R). The interpolation formula is usually index-based (ref this comment), but a matrix-based formulation is recently proposed, which seems better suited for GraphBLAS's programming style.

I don't think there are any fundamental roadblocks to any of these methods. It should be possible to write a high-performance AMG for LAGraph+GraphBLAS.

This is good to hear, and it seems an interesting but unexplored research topic. From the information I gathered above, the basic build blocks are there, but need to be modified to express the actual AMG formula. I haven't figured out how to do so. Maybe leave this issue open for further thoughts/progresses. :)