# Fast Linear Solvers via AI-Tuned Markov Chain Monte Carlo-based Matrix Inversion

arXiv: https://arxiv.org/abs/2509.18452 · HTML: https://mlsanity.com/paper/2509.18452/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 22 Sep 2025.

## Builds on (most cited first, 10 of 10)

- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [When Gaussian Process Meets Big Data: A Review of Scalable GPs](https://mlsanity.com/paper/1807.01065/) (2018)
- [A System for Massively Parallel Hyperparameter Tuning](https://mlsanity.com/paper/1810.05934/) (2018)
- [Graph Neural Networks with Adaptive Readouts](https://mlsanity.com/paper/2211.04952/) (2022)
- [Graph Neural Preconditioners for Iterative Solutions of Sparse Linear Systems](https://mlsanity.com/paper/2406.00809/) (2024)
- [On Advanced Monte Carlo Methods for Linear Algebra on Advanced Accelerator Architectures](https://mlsanity.com/paper/2409.03095/) (2024)

## Abstract (arXiv)

Large, sparse linear systems are pervasive in modern science and engineering, and Krylov subspace solvers are an established means of solving them. Yet convergence can be slow for ill-conditioned matrices, so practical deployments usually require preconditioners. Markov chain Monte Carlo (MCMC)-based matrix inversion can generate such preconditioners and accelerate Krylov iterations, but its effectiveness depends on parameters whose optima vary across matrices; manual or grid search is costly. We present an AI-driven framework recommending MCMC parameters for a given linear system. A graph neural surrogate predicts preconditioning speed from A and MCMC parameters. A Bayesian acquisition function then chooses the parameter sets most likely to minimise iterations. On a previously unseen ill-conditioned system, the framework achieves better preconditioning with 50% of the search budget of conventional methods, yielding about a 10% reduction in iterations to convergence. These results suggest a route for incorporating MCMC-based preconditioners into large-scale systems.