Learning Algebraic Multigrid Using Graph Neural Networks

• URL: http://arxiv.org/abs/2003.05744v2
• Date: Thu, 24 Sep 2020 09:23:34 GMT
• Title: Learning Algebraic Multigrid Using Graph Neural Networks
• Authors: Ilay Luz, Meirav Galun, Haggai Maron, Ronen Basri, Irad Yavneh
• Abstract summary: We train a single graph neural network to learn a mapping from an entire class of such matrices to prolongation operators. Experiments on a broad class of problems demonstrate improved convergence rates compared to classical AMG.
• Score: 34.32501734380907
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Efficient numerical solvers for sparse linear systems are crucial in science and engineering. One of the fastest methods for solving large-scale sparse linear systems is algebraic multigrid (AMG). The main challenge in the construction of AMG algorithms is the selection of the prolongation operator -- a problem-dependent sparse matrix which governs the multiscale hierarchy of the solver and is critical to its efficiency. Over many years, numerous methods have been developed for this task, and yet there is no known single right answer except in very special cases. Here we propose a framework for learning AMG prolongation operators for linear systems with sparse symmetric positive (semi-) definite matrices. We train a single graph neural network to learn a mapping from an entire class of such matrices to prolongation operators, using an efficient unsupervised loss function. Experiments on a broad class of problems demonstrate improved convergence rates compared to classical AMG, demonstrating the potential utility of neural networks for developing sparse system solvers.

Related papers

• Compute Better Spent: Replacing Dense Layers with Structured Matrices [77.61728033234233]
  We identify more efficient alternatives to dense matrices, as exemplified by the success of convolutional networks in the image domain. We show that different structures often require drastically different initialization scales and learning rates, which are crucial to performance. We propose a novel matrix family containing Monarch matrices, the Block-Train, which we show performs better than dense for the same compute on multiple tasks.
  arXiv  Detail & Related papers  (2024-06-10T13:25:43Z)
• Linear Recursive Feature Machines provably recover low-rank matrices [17.530511273384786]
  We develop the first theoretical guarantees for how RFM performs dimensionality reduction. We generalize the Iteratively Reweighted Least Squares (IRLS) algorithm. Our results shed light on the connection between feature learning in neural networks and classical sparse recovery algorithms.
  arXiv  Detail & Related papers  (2024-01-09T13:44:12Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA. By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms. We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-06T14:59:38Z)
• A Deep Learning algorithm to accelerate Algebraic Multigrid methods in Finite Element solvers of 3D elliptic PDEs [0.0]
  We introduce a novel Deep Learning algorithm that minimizes the computational cost of the Algebraic multigrid method when used as a finite element solver. We experimentally prove that the pooling successfully reduces the computational cost of processing a large sparse matrix and preserves the features needed for the regression task at hand.
  arXiv  Detail & Related papers  (2023-04-21T09:18:56Z)
• RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations [56.59168541623729]
  Training graph neural networks (GNNs) is time consuming because sparse graph-based operations are hard to be accelerated by hardware. We explore trading off the computational precision to reduce the time complexity via sampling-based approximation. We propose Randomized Sparse Computation, which for the first time demonstrate the potential of training GNNs with approximated operations.
  arXiv  Detail & Related papers  (2022-10-19T17:25:33Z)
• Towards Neural Sparse Linear Solvers [0.0]
  We propose neural sparse linear solvers to learn approximate solvers for sparse symmetric linear systems. Our method relies on representing a sparse symmetric linear system as an undirected weighted graph. We test sparse linear solvers on static linear analysis problems from structural engineering.
  arXiv  Detail & Related papers  (2022-03-14T09:17:02Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning [0.0]
  A system of linear equations defines a graph on the set of unknowns. Each level of a multigrid solver requires the selection of an appropriate coarse graph along with restriction and operators that map to and from the coarse representation. It has been demonstrated that it is possible to directly learn the AMG and restriction operators, given a coarse graph selection. We propose a sparse method using a reinforcement learning agent based on graph neural networks (GNNs)
  arXiv  Detail & Related papers  (2021-06-03T13:57:32Z)
• Joint Deep Reinforcement Learning and Unfolding: Beam Selection and Precoding for mmWave Multiuser MIMO with Lens Arrays [54.43962058166702]
  millimeter wave (mmWave) multiuser multiple-input multiple-output (MU-MIMO) systems with discrete lens arrays have received great attention. In this work, we investigate the joint design of a beam precoding matrix for mmWave MU-MIMO systems with DLA.
  arXiv  Detail & Related papers  (2021-01-05T03:55:04Z)
• GL-Coarsener: A Graph representation learning framework to construct coarse grid hierarchy for AMG solvers [0.0]
  Algebraic multi-grid (AMG) methods are numerical methods used to solve large linear systems of equations efficiently. Here we propose an aggregation-based coarsening framework leveraging graph representation learning and clustering algorithms. Our method introduces the power of machine learning into the AMG research field and opens a new perspective for future researches.
  arXiv  Detail & Related papers  (2020-11-19T17:49:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.