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

• URL: http://arxiv.org/abs/2509.18452v1
• Date: Mon, 22 Sep 2025 22:14:13 GMT
• Title: Fast Linear Solvers via AI-Tuned Markov Chain Monte Carlo-based Matrix Inversion
• Abstract summary: We present an AI-driven framework recommending MCMC parameters for a given linear system.<n>A graph neural surrogate predicts preconditioning speed from $A$ and MCMC parameters.<n>On a previously unseen ill-conditioned system, the framework achieves better preconditioning with 50% of the search budget of conventional methods.
• Score: 8.596794810605124
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• When Model Merging Breaks Routing: Training-Free Calibration for MoE [67.27839627141972]
  Hessian-Aware Router (HARC) is a training-free framework that leverages second-order curvature information to realign the merged router.<n> Experiments on mathematical reasoning and code generation tasks show that HARC effectively mitigates routing breakdown across diverse MoE merging baselines.
  arXiv  Detail & Related papers  (2026-06-02T09:33:33Z)
• High-dimensional Adaptive MCMC with Reduced Computational Complexity [0.8594140167290097]
  We propose an adaptive MCMC method that learns a linear preconditioner which is dense in its off-diagonal elements but sparse in its parametrisation.<n>We show that it outperforms diagonal preconditioning in terms of absolute performance.
  arXiv  Detail & Related papers  (2026-04-10T12:58:00Z)
• MaRI: Accelerating Ranking Model Inference via Structural Re-parameterization in Large Scale Recommendation System [24.4139949756995]
  We propose MaRI, a novel Matrix Re- Parametersized Inference framework.<n>It serves as a complementary approach to existing techniques while accelerating ranking model inference without any accuracy loss.<n>MaRI is motivated by the observation that user-side computation is redundant in feature fusion matrix multiplication.
  arXiv  Detail & Related papers  (2026-02-26T15:19:43Z)
• Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models [68.31088463716269]
  We propose a structured sparse parametrization of transition matrices in state-space models (SSMs)<n>Our method, PD-SSM, parametrizes the transition matrix as the product of a column one-hot matrix ($P$) and a complex-valued diagonal matrix ($D$)<n>The model significantly outperforms a wide collection of modern SSM variants on various FSA state tracking tasks.
  arXiv  Detail & Related papers  (2025-09-26T12:46:30Z)
• Matrix-free Neural Preconditioner for the Dirac Operator in Lattice Gauge Theory [13.32375374102012]
  We propose a framework, leveraging operator learning techniques, to construct linear maps as effective preconditioners.<n>In the context of the Schwinger model U(1) gauge theory in 1+1 spacetime dimensions, this preconditioning scheme effectively decreases the condition number of the linear systems.
  arXiv  Detail & Related papers  (2025-09-12T16:10:18Z)
• LoRTA: Low Rank Tensor Adaptation of Large Language Models [70.32218116940393]
  Low Rank Adaptation (LoRA) is a popular Efficient Fine Tuning (PEFT) method.<n>We propose a higher-order Candecomp/Parafac (CP) decomposition, enabling a more compact and flexible representation.<n>Our method can achieve a reduction in the number of parameters while maintaining comparable performance.
  arXiv  Detail & Related papers  (2024-10-05T06:59:50Z)
• Parameter-Adaptive Approximate MPC: Tuning Neural-Network Controllers without Retraining [50.00291020618743]
  This work introduces a novel, parameter-adaptive AMPC architecture capable of online tuning without recomputing large datasets and retraining. We showcase the effectiveness of parameter-adaptive AMPC by controlling the swing-ups of two different real cartpole systems with a severely resource-constrained microcontroller (MCU) Taken together, these contributions represent a marked step toward the practical application of AMPC in real-world systems.
  arXiv  Detail & Related papers  (2024-04-08T20:02:19Z)
• Large-Scale OD Matrix Estimation with A Deep Learning Method [70.78575952309023]
  The proposed method integrates deep learning and numerical optimization algorithms to infer matrix structure and guide numerical optimization. We conducted tests to demonstrate the good generalization performance of our method on a large-scale synthetic dataset.
  arXiv  Detail & Related papers  (2023-10-09T14:30:06Z)
• Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
  We show that a bandit online learning algorithm can select parameters for a sequence of instances such that the overall cost approaches that of the best fixed $omega$ as the sequence length increases. Our work provides the first learning-theoretic treatment of high-precision linear system solvers and the first end-to-end guarantees for data-driven scientific computing.
  arXiv  Detail & Related papers  (2023-10-03T17:51:42Z)
• Formal Controller Synthesis for Markov Jump Linear Systems with Uncertain Dynamics [64.72260320446158]
  We propose a method for synthesising controllers for Markov jump linear systems. Our method is based on a finite-state abstraction that captures both the discrete (mode-jumping) and continuous (stochastic linear) behaviour of the MJLS. We apply our method to multiple realistic benchmark problems, in particular, a temperature control and an aerial vehicle delivery problem.
  arXiv  Detail & Related papers  (2022-12-01T17:36:30Z)
• Online Probabilistic Model Identification using Adaptive Recursive MCMC [8.465242072268019]
  We suggest the Adaptive Recursive Markov Chain Monte Carlo (ARMCMC) method. It eliminates the shortcomings of conventional online techniques while computing the entire probability density function of model parameters. We demonstrate our approach using parameter estimation in a soft bending actuator and the Hunt-Crossley dynamic model.
  arXiv  Detail & Related papers  (2022-10-23T02:06:48Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• An adaptive Hessian approximated stochastic gradient MCMC method [12.93317525451798]
  We present an adaptive Hessian approximated gradient MCMC method to incorporate local geometric information while sampling from the posterior. We adopt a magnitude-based weight pruning method to enforce the sparsity of the network.
  arXiv  Detail & Related papers  (2020-10-03T16:22:15Z)

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.