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

Large, sparse linear systems are pervasive in modern science and engineering, and Krylov subspace solvers provide an established means to solve them efficiently. Nonetheless, the convergence of Krylov subspace methods in particular, and iterative methods in general, can be quite slow when the iteration matrix is ill‑conditioned. Thus, practical deployments of Krylov subspace solvers usually rely on a suitable preconditioner. Markov chain Monte Carlo (MCMC)-based matrix inversion methods have been proposed to generate such preconditioners and can substantially accelerate Krylov iterations, yet their effectiveness is governed by a small set of algorithmic hyperparameters whose optimal values vary from one matrix to the next. Discovering those values either manually or by a grid search is costly and requires a vast number of time‑consuming trials, thereby limiting the wider adoption of MCMC‑based preconditioning. In this paper, we present an AI‑driven framework that automatically recommends MCMC parameters for a given sparse system of linear algebraic equations. At the core of our framework lies a graph‑neural surrogate model that, for any pair comprising an iteration matrix $A$ and a candidate of MCMC algorithmic parameters, predicts the resulting preconditioning speed. A Bayesian acquisition function then uses these predictions and their uncertainties to choose, in each batch, the parameter sets most likely to minimise the expected iteration count, while the evaluation overhead of the surrogate itself remains negligible. When applied to previously unseen sparse systems, the proposed framework achieves better preconditioning performance with only half the search budget required by conventional methods, yielding about a 10% reduction in the number of iterations to achieve converegence. The results suggest a practical route for incorporating MCMC-based preconditioners into solving large-scale linear systems.