Learning to Select Sparse Linear Solvers with Convolutional Neural Networks
Authors: Artemis Pados, Alan Edelman, Emmanuel Lujan, Daniel Pickard, Felipe Tome, Christopher Rackauckas
Organizations: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, USA. · Computer Science & Artificial Intelligence Laboratory, Massachusetts Institute of Technology, USA. · Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, USA.
We investigate convolutional-neural-network (CNN) based automatic solver selection for sparse linear systems, a problem of practical importance where solver performance varies dramatically with matrix sparsity structure. A CNN is trained to regress log timing ratios between candidate solvers using spy plot images of matrix nonzero structure as input, achieving strong prediction accuracy on both held-out SuiteSparse matrices and real-world matrices from high-performance simulation codes.
Figures & tables
Fig. 1: Normalized confusion matrices for SuiteSparse holdout (left) and CHEFSI/ Σ MIT evaluation (right).
We introduce AutoSpec, a neural network framework for discovering iterative spectral algorithms for large-scale numerical linear algebra and numerical optimization. Our self-supervised models adapt to input operators using coarse spectral information (e.g., eigenvalue estimates and residual norms), and predict recurrence coefficients for computing or applying a matrix polynomial tailored to a downstream task. The effectiveness of AutoSpec relies on three ingredients: an architecture whose inference pass implements short, executable numerical linear algebra recurrences; efficient training on small synthetic problems with transfer to large-scale real-world operators; and task-defined objectives that enforce the desired approximation or preconditioning behavior across the range of spectral profiles represented in the training set. We apply AutoSpec to discovering algorithms for representative tasks on spd matrices: accelerating matrix function approximation; accelerating sparse linear solvers; and spectral filtering/preconditioning for eigenvalue computations. On real-world matrices, the learned procedures deliver up to order-of-magnitude improvements in accuracy and/or reductions in iteration count, relative to spectrum-agnostic baselines. We find clear connections to classical theory: the induced polynomials may exhibit equioscillation behavior characteristic of Chebyshev polynomial approximation. The code is available at: https://github.com/zihanghliu/AutoSpec .
Zihang Liu, Oleg Balabanov, Yaoqing Yang +1
1International Computer Science Institute · University of California, Berkeley · 4Lawrence Berkeley National Laboratory +1
In this paper, we propose a fast method for estimating the condition number of sparse matrices using graph neural networks (GNNs). For efficient deployment of GNNs, we introduce a graph feature construction with O(nnz+n) complexity, where nnz is the number of non-zero elements in the matrix and n denotes the matrix dimension. We propose two schemes for estimating the matrix condition number using GNNs; one follows by decomposing the condition number and predicts the relatively more computationally intensive part ∥A−1∥, without explicitly forming the inverse, while the other is to predict the whole condition number κ. Our approach can be extended to an arbitrary norm. Extensive experiments are conducted for the estimation of the 1-norm and 2-norm condition numbers, which show that our method achieves a significant speedup over the traditional numerical estimation methods. Our software for GNN condition number estimator is made publicly available at https://github.com/inEXASCALE/sparse-kappa.
Erin Carson, Xinye Chen
Charles University, Prague, Czech Republic · Sorbonne Université, CNRS, LIP6, Paris, France
Neural subspace solvers offer a promising way to accelerate the large sparse linear systems arising from PDE discretizations, but their value depends on generating effective correction directions at low computational overheads. We study this problem from a residual-image viewpoint: a correction subspace is useful when its image under the system operator captures the current residual. Guided by this view, we propose Gate-RINS, which generates multiple correction directions from shared polynomial residual probes and modulates them with a lightweight residual- and coordinate-dependent pointwise gate. We also introduce a hybrid schedule that uses GRANS-style graph controllers for the first correction block and Gate-RINS thereafter, combining an expressive graph based initial step with a lower-cost corrector as the solve progress. Theoretical analysis establishes a unified residual-image and dynamic approximate-inverse perspective for Gate-RINS and G-RANS, showing that a single neural-generated direction can emulate the residual quality of fixed-step GMRES. Numerical experiments on six PDE benchmarks demonstrate that Gate-RINS reaches a relative residual of 10−5 with 1.6-2.3× and 2.2-3.0× less wall-clock time than G-RANS and GMRES respectively. For Helmholtz systems with meshsize up to 105, Gate-RINS also achieves the lowest residual and outperforms a GPU-accelerated parallel GMRES, while GRANS fails to reach relative residual of 10−4 in the same time budget.
Zhongyan Ouyang, Weixin Liao, Mingquan Feng +2
Shanghai Innovation Institute, Shanghai, China · Faculty of Computation, Harbin Institute of Technology, Harbin, China · School of Artificial Intelligence and School of Computer Science, Shanghai Jiao Tong University, Shanghai, China +1