Workshops Archive

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

Workshop: 16th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Heterogeneous Systems (ScalAH'25)

Authors: Anton Lebedev and Won Kyung Lee (STFC Hartree Centre); Soumyadip Ghosh (IBM Thomas J. Watson Research Center); Olha I. Yaman (STFC Hartree Centre); Vassilis Kalantzis, Yingdong Lu, Tomasz Nowicki, Shashanka Ubaru, and Lior Horesh (IBM Thomas J. Watson Research Center); and Vassil Alexandrov (STFC Hartree Centre)

Abstract: 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.

Back to 16th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Heterogeneous Systems (ScalAH'25) Archive Listing Back to Full Workshop Archive Listing