Lune

NeurIPS2021Top-tier venue

Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning

Ali Taghibakhshi, Scott P. MacLachlan, Luke N. Olson, Matthew West

Abstract

Large sparse linear systems of equations are ubiquitous in science and engineering, such as those arising from discretizations of partial differential equations. Algebraic multigrid (AMG) methods are one of the most common methods of solving such linear systems, with an extensive body of underlying mathematical theory. A system of linear equations defines a graph on the set of unknowns and each level of a multigrid solver requires the selection of an appropriate coarse graph along with restriction and interpolation operators that map to and from the coarse representation. The efficiency of the multigrid solver depends critically on this selection and many selection methods have been developed over the years. Recently, it has been demonstrated that it is possible to directly learn the AMG interpolation and restriction operators, given a coarse graph selection. In this paper, we consider the complementary problem of learning to coarsen graphs for a multigrid solver, a necessary step in developing fully learnable AMG methods. We propose a method using a reinforcement learning (RL) agent based on graph neural networks (GNNs), which can learn to perform graph coarsening on small planar training graphs and then be applied to unstructured large planar graphs, assuming bounded node degree. We demonstrate that this method can produce better coarse graphs than existing algorithms, even as the graph size increases and other properties of the graph are varied. We also propose an efficient inference procedure for performing graph coarsening that results in linear time complexity in graph size.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

9 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Neural Krylov Iteration for Accelerating Linear System Solving cites Learning Algebraic Multigrid Using Graph Neural Networks
  • Learning Sparse Approximate Inverse Preconditioners for Conjugate Gradient Solvers on GPUs cites Neural Krylov Iteration for Accelerating Linear System Solving
  • Learning Interface Conditions in Domain Decomposition Solvers cites Learning Algebraic Multigrid Using Graph Neural Networks
  • MG-GNN: Multigrid Graph Neural Networks for Learning Multilevel Domain Decomposition Methods cites Learning Algebraic Multigrid Using Graph Neural Networks
  • MG-GNN: Multigrid Graph Neural Networks for Learning Multilevel Domain Decomposition Methods cites Learning Interface Conditions in Domain Decomposition Solvers
  • SymMaP: Improving Computational Efficiency in Linear Solvers through Symbolic Preconditioning cites Learning Algebraic Multigrid Using Graph Neural Networks
  • SymMaP: Improving Computational Efficiency in Linear Solvers through Symbolic Preconditioning cites Neural Krylov Iteration for Accelerating Linear System Solving
  • SymMaP: Improving Computational Efficiency in Linear Solvers through Symbolic Preconditioning cites Learning Sparse Approximate Inverse Preconditioners for Conjugate Gradient Solvers on GPUs
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers9

  1. Neural Krylov Iteration for Accelerating Linear System SolvingJian Luo, Jie Wang, Hong Wang, Huanshuo Dong et al.NeurIPS 2024 · 23 citations
  2. Learning Interface Conditions in Domain Decomposition SolversAli Taghibakhshi, Nicolas Nytko, Tareq Uz Zaman, Scott P. MacLachlan et al.NeurIPS 2022 · 18 citations
  3. MG-GNN: Multigrid Graph Neural Networks for Learning Multilevel Domain Decomposition MethodsAli Taghibakhshi, Nicolas Nytko, Tareq Uz Zaman, Scott P. MacLachlan et al.ICML 2023 · 16 citations
  4. SymMaP: Improving Computational Efficiency in Linear Solvers through Symbolic PreconditioningHong Wang, Jie Wang, Minghao Ma, Haoran Shao et al.NeurIPS 2025 · 6 citations
  5. Learning Sparse Approximate Inverse Preconditioners for Conjugate Gradient Solvers on GPUsZhehao Li, Kangbo Lyu, Yixuan Li, Tao Du et al.NeurIPS 2025 · 5 citations

Builds on1

  1. Learning Algebraic Multigrid Using Graph Neural NetworksIlay Luz, Meirav Galun, Haggai Maron, Ronen Basri et al.ICML 2020 · 95 citations

Related papers

  1. RAPNet: Accelerating Algebraic Multigrid with Learned Sparse CorrectionsYali Fink, Ido Ben-Yair, Lars Ruthotto, Eran TreisterICML 2026
  2. Graph Neural Preconditioners for Iterative Solutions of Sparse Linear SystemsJie ChenICLR 2025
  3. Graph Coarsening with Neural NetworksChen Cai, Dingkang Wang, Yusu WangICLR 2021 · 13 citations
  4. Bridging Training and Execution via Dynamic Directed Graph-Based Communication in Cooperative Multi-Agent SystemsZhuohui Zhang, Bin He, Bin Cheng, Gang LiAAAI 2025 · 10 citations
  5. MAG-GNN: Reinforcement Learning Boosted Graph Neural NetworkLecheng Kong, Jiarui Feng, Hao Liu, Dacheng Tao et al.NeurIPS 2023 · 24 citations
Dusk over the sea between two cliffs drawn in fine vertical lines