Learning Sparse Approximate Inverse Preconditioners for Conjugate Gradient Solvers on GPUs

• URL: http://arxiv.org/abs/2510.27517v1
• Date: Fri, 31 Oct 2025 14:42:48 GMT
• Title: Learning Sparse Approximate Inverse Preconditioners for Conjugate Gradient Solvers on GPUs
• Authors: Zherui Yang, Zhehao Li, Kangbo Lyu, Yixuan Li, Tao Du, Ligang Liu,
• Abstract summary: Concomitant gradient solver (CG) is a prevalent method for solving symmetric and positive definite linear systems Ax=b.<n>Existing learning-based methods often utilize Graph Neural Networks (GNNs) to improve the performance and speed up the construction.<n>We propose a learning-based method to generate GPU-friendly preconditioners, particularly using GNNs to construct Sparse Approximate Inverse (SPAI) preconditioners.
• Score: 25.22023084590467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The conjugate gradient solver (CG) is a prevalent method for solving symmetric and positive definite linear systems Ax=b, where effective preconditioners are crucial for fast convergence. Traditional preconditioners rely on prescribed algorithms to offer rigorous theoretical guarantees, while limiting their ability to exploit optimization from data. Existing learning-based methods often utilize Graph Neural Networks (GNNs) to improve the performance and speed up the construction. However, their reliance on incomplete factorization leads to significant challenges: the associated triangular solve hinders GPU parallelization in practice, and introduces long-range dependencies which are difficult for GNNs to model. To address these issues, we propose a learning-based method to generate GPU-friendly preconditioners, particularly using GNNs to construct Sparse Approximate Inverse (SPAI) preconditioners, which avoids triangular solves and requires only two matrix-vector products at each CG step. The locality of matrix-vector product is compatible with the local propagation mechanism of GNNs. The flexibility of GNNs also allows our approach to be applied in a wide range of scenarios. Furthermore, we introduce a statistics-based scale-invariant loss function. Its design matches CG's property that the convergence rate depends on the condition number, rather than the absolute scale of A, leading to improved performance of the learned preconditioner. Evaluations on three PDE-derived datasets and one synthetic dataset demonstrate that our method outperforms standard preconditioners (Diagonal, IC, and traditional SPAI) and previous learning-based preconditioners on GPUs. We reduce solution time on GPUs by 40%-53% (68%-113% faster), along with better condition numbers and superior generalization performance. Source code available at https://github.com/Adversarr/LearningSparsePreconditioner4GPU

Related papers

• nuGPR: GPU-Accelerated Gaussian Process Regression with Iterative Algorithms and Low-Rank Approximations [3.8715578341717207]
  We propose a new framework, nuGPR, to address the challenge of high cost associated with GPR training.<n>Our framework includes several ideas from numerical linear algebra to reduce the amount of computation in key steps of GPR, and we combine them to establish an end-to-end training algorithm.<n> nuGPR reduces total training time by up to 2x and peak memory consumption by up to 12x on various synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2025-10-14T04:06:02Z)
• Geometric Algebra Planes: Convex Implicit Neural Volumes [70.12234371845445]
  We show that GA-Planes is equivalent to a sparse low-rank factor plus low-resolution matrix. We also show that GA-Planes can be adapted for many existing representations.
  arXiv  Detail & Related papers  (2024-11-20T18:21:58Z)
• Learning incomplete factorization preconditioners for GMRES [1.1519724914285523]
  We train a graph neural network to approximate the matrix factorization directly.<n>Applying a graph neural network architecture allows us to ensure that the output itself is sparse.<n>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.<n>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)
• Multi-Level GNN Preconditioner for Solving Large Scale Problems [0.0]
  Graph Neural Networks (GNNs) are great for learning from unstructured data like meshes but are often limited to small-scale problems. This paper introduces a novel preconditioner integrating a GNN model within a multi-level Domain Decomposition framework. The proposed GNN-based preconditioner is used to enhance the efficiency of a Krylov method, resulting in a hybrid solver that can converge with any desired level of accuracy.
  arXiv  Detail & Related papers  (2024-02-13T08:50:14Z)
• Curvature-Informed SGD via General Purpose Lie-Group Preconditioners [6.760212042305871]
  We present a novel approach to accelerate gradient descent (SGD) by utilizing curvature information. Our approach involves two preconditioners: a matrix-free preconditioner and a low-rank approximation preconditioner. We demonstrate that Preconditioned SGD (PSGD) outperforms SoTA on Vision, NLP, and RL tasks.
  arXiv  Detail & Related papers  (2024-02-07T03:18:00Z)
• GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
  We present a novel approach to non-cube optimization with certificates, which handles smooth functions on the hypercube or on the torus. By exploiting the regularity of the target function intrinsic in the decay of its spectrum, we allow at the same time to obtain precise certificates and leverage the advanced and powerful neural networks.
  arXiv  Detail & Related papers  (2023-06-26T09:42:59Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• Why Approximate Matrix Square Root Outperforms Accurate SVD in Global Covariance Pooling? [59.820507600960745]
  We propose a new GCP meta-layer that uses SVD in the forward pass, and Pad'e Approximants in the backward propagation to compute the gradients. The proposed meta-layer has been integrated into different CNN models and achieves state-of-the-art performances on both large-scale and fine-grained datasets.
  arXiv  Detail & Related papers  (2021-05-06T08:03:45Z)
• GradInit: Learning to Initialize Neural Networks for Stable and Efficient Training [59.160154997555956]
  We present GradInit, an automated and architecture method for initializing neural networks. It is based on a simple agnostic; the variance of each network layer is adjusted so that a single step of SGD or Adam results in the smallest possible loss value. It also enables training the original Post-LN Transformer for machine translation without learning rate warmup.
  arXiv  Detail & Related papers  (2021-02-16T11:45:35Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)

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.