Learning incomplete factorization preconditioners for GMRES

• URL: http://arxiv.org/abs/2409.08262v2
• Date: Wed, 11 Dec 2024 12:23:37 GMT
• Title: Learning incomplete factorization preconditioners for GMRES
• Authors: Paul Häusner, Aleix Nieto Juscafresa, Jens Sjölund,
• Abstract summary: 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.
• Score: 1.1519724914285523
• License:
• Abstract: Incomplete LU factorizations of sparse matrices are widely used as preconditioners in Krylov subspace methods to speed up solving linear systems. Unfortunately, computing the preconditioner itself can be time-consuming and sensitive to hyper-parameters. Instead, we replace the hand-engineered algorithm with a graph neural network that is trained to approximate the matrix factorization directly. To apply the output of the neural network as a preconditioner, we propose an output activation function that guarantees that the predicted factorization is invertible. Further, applying a graph neural network architecture allows us to ensure that the output itself is sparse which is desirable from a computational standpoint. We theoretically analyze and empirically evaluate different loss functions to train the learned preconditioners and show their effectiveness in decreasing the number of GMRES iterations and improving the spectral properties on synthetic data. The code is available at https://github.com/paulhausner/neural-incomplete-factorization.

Related papers

• 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)
• 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)
• The Decimation Scheme for Symmetric Matrix Factorization [0.0]
  Matrix factorization is an inference problem that has acquired importance due to its vast range of applications. We study this extensive rank problem, extending the alternative 'decimation' procedure that we recently introduced. We introduce a simple algorithm based on a ground state search that implements decimation and performs matrix factorization.
  arXiv  Detail & Related papers  (2023-07-31T10:53:45Z)
• Neural incomplete factorization: learning preconditioners for the conjugate gradient method [2.899792823251184]
  We develop a data-driven approach to accelerate the generation of effective preconditioners. We replace the typically hand-engineered preconditioners by the output of graph neural networks. Our method generates an incomplete factorization of the matrix and is, therefore, referred to as neural incomplete factorization (NeuralIF)
  arXiv  Detail & Related papers  (2023-05-25T11:45:46Z)
• Variable Bitrate Neural Fields [75.24672452527795]
  We present a dictionary method for compressing feature grids, reducing their memory consumption by up to 100x. We formulate the dictionary optimization as a vector-quantized auto-decoder problem which lets us learn end-to-end discrete neural representations in a space where no direct supervision is available.
  arXiv  Detail & Related papers  (2022-06-15T17:58:34Z)
• Convolutional generative adversarial imputation networks for spatio-temporal missing data in storm surge simulations [86.5302150777089]
  Generative Adversarial Imputation Nets (GANs) and GAN-based techniques have attracted attention as unsupervised machine learning methods. We name our proposed method as Con Conval Generative Adversarial Imputation Nets (Conv-GAIN)
  arXiv  Detail & Related papers  (2021-11-03T03:50:48Z)
• Meta-Solver for Neural Ordinary Differential Equations [77.8918415523446]
  We investigate how the variability in solvers' space can improve neural ODEs performance. We show that the right choice of solver parameterization can significantly affect neural ODEs models in terms of robustness to adversarial attacks.
  arXiv  Detail & Related papers  (2021-03-15T17:26:34Z)
• 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)
• Activation Relaxation: A Local Dynamical Approximation to Backpropagation in the Brain [62.997667081978825]
  Activation Relaxation (AR) is motivated by constructing the backpropagation gradient as the equilibrium point of a dynamical system. Our algorithm converges rapidly and robustly to the correct backpropagation gradients, requires only a single type of computational unit, and can operate on arbitrary computation graphs.
  arXiv  Detail & Related papers  (2020-09-11T11:56:34Z)
• Predictive Coding Approximates Backprop along Arbitrary Computation Graphs [68.8204255655161]
  We develop a strategy to translate core machine learning architectures into their predictive coding equivalents. Our models perform equivalently to backprop on challenging machine learning benchmarks. Our method raises the potential that standard machine learning algorithms could in principle be directly implemented in neural circuitry.
  arXiv  Detail & Related papers  (2020-06-07T15:35:47Z)

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.