Graph Neural Preconditioners for Iterative Solutions of Sparse Linear Systems

• URL: http://arxiv.org/abs/2406.00809v3
• Date: Sun, 26 Jan 2025 22:21:05 GMT
• Title: Graph Neural Preconditioners for Iterative Solutions of Sparse Linear Systems
• Authors: Jie Chen,
• Abstract summary: We propose using graph neural networks as a general-purpose preconditioner. They show attractive performance for many problems and can be used when the mainstream preconditioners perform poorly.
• Score: 5.083469153675402
• License:
• Abstract: Preconditioning is at the heart of iterative solutions of large, sparse linear systems of equations in scientific disciplines. Several algebraic approaches, which access no information beyond the matrix itself, are widely studied and used, but ill-conditioned matrices remain very challenging. We take a machine learning approach and propose using graph neural networks as a general-purpose preconditioner. They show attractive performance for many problems and can be used when the mainstream preconditioners perform poorly. Empirical evaluation on over 800 matrices suggests that the construction time of these graph neural preconditioners (GNPs) is more predictable and can be much shorter than that of other widely used ones, such as ILU and AMG, while the execution time is faster than using a Krylov method as the preconditioner, such as in inner-outer GMRES. GNPs have a strong potential for solving large-scale, challenging algebraic problems arising from not only partial differential equations, but also economics, statistics, graph, and optimization, to name a few.

Related papers

• ReFill: Reinforcement Learning for Fill-In Minimization [3.9134031118910264]
  Minimizing fill-in is NP-hard, and existing minimizations like Minimum Degree and Nested Dissection offer limited adaptability. We introduce textitReFill, a reinforcement learning framework enhanced by Graph Neural Networks (GNNs) to learn adaptive ordering strategies for fill-in.
  arXiv  Detail & Related papers  (2025-01-27T15:20:41Z)
• Learning incomplete factorization preconditioners for GMRES [1.1519724914285523]
  We train a graph neural network to approximate the matrix factorization directly. Applying a graph neural network architecture allows us to ensure that the output itself is sparse. We show their effectiveness in decreasing the number of GMRES iterations and improving the spectral properties on synthetic data.
  arXiv  Detail & Related papers  (2024-09-12T17:55:44Z)
• Learning from Linear Algebra: A Graph Neural Network Approach to Preconditioner Design for Conjugate Gradient Solvers [40.6591136324878]
  We train GNNs to obtain preconditioners that reduce the condition number of the system more significantly than classical preconditioners. Our approach outperforms both classical and neural network-based methods for an important class of parametric partial differential equations.
  arXiv  Detail & Related papers  (2024-05-24T13:44:30Z)
• Neural Time-Reversed Generalized Riccati Equation [60.92253836775246]
  Hamiltonian equations offer an interpretation of optimality through auxiliary variables known as costates. This paper introduces a novel neural-based approach to optimal control, with the aim of working forward-in-time.
  arXiv  Detail & Related papers  (2023-12-14T19:29:37Z)
• Graph Neural Networks and Applied Linear Algebra [1.8749305679160366]
  Graph neural networks (GNNs) are an approach suitable to sparse matrix computations. This paper provides an introduction to GNNs for a numerical linear algebra audience. Concrete examples are provided to illustrate how many common linear algebra tasks can be accomplished using GNNs.
  arXiv  Detail & Related papers  (2023-10-21T18:37:56Z)
• 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)
• Deep learning applied to computational mechanics: A comprehensive review, state of the art, and the classics [77.34726150561087]
  Recent developments in artificial neural networks, particularly deep learning (DL), are reviewed in detail. Both hybrid and pure machine learning (ML) methods are discussed. History and limitations of AI are recounted and discussed, with particular attention at pointing out misstatements or misconceptions of the classics.
  arXiv  Detail & Related papers  (2022-12-18T02:03:00Z)
• 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)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73%.
  arXiv  Detail & Related papers  (2022-05-27T17:13:10Z)
• Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
  We present a totally different approach to the problem, which is competitive and often orders of magnitude better than the prior state of the art. With experiments on poker endgames, we demonstrate, for the first time, that modern linear program solvers are competitive against even game-specific modern variants of CFR.
  arXiv  Detail & Related papers  (2020-06-05T13:48:26Z)
• Learning Algebraic Multigrid Using Graph Neural Networks [34.32501734380907]
  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.
  arXiv  Detail & Related papers  (2020-03-12T12:36:48Z)

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.