Learning to Solve Related Linear Systems
2025
Read Learning to Solve Related Linear Systems (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-17265.txt.
Introduction
Many number tasks boil down to solving the same web of equations again and again, with small shifts in a dial. Hegde and Cockayne speed that loop in 2025 by letting each solved web teach the next. Their solver treats the dial's space as a field for a kind of regression.
The learned model gives both a best guess for the next answer and a spread of doubt around it. Fed to a classic solver as its start point and its shaping tool, the guess can cut the work left to do. The pair lay out the design picks for the learned partner. Tests on a problem of tuning a model's own dials show the gain. The pitch is a solver that grows sharper the more webs it has seen.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-17265
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning to Solve Related Linear Systems Abstract Solving multiple parametrised related systems is an essential component of many numerical tasks. Borrowing strength from the solved systems and learning will make this process faster. In this work, we propose a novel probabilistic linear solver over the parameter space. This leverages information from the solved linear systems in a regression setting to provide an efficient posterior mean and covariance. We advocate using this as companion regression model for the preconditioned conjugate gradient method, and discuss the favourable properties of the posterior mean and covariance as the initial guess and preconditioner. We also provide several design choices for this companion solver. Numerical experiments showcase the benefits of using our novel solver in a hyperparameter optimisation problem. 1 Introduction We consider the problem of solving multiple related linear systems. Suppose that these linear systems vary according to some governing parameter \theta\in\Theta . Then the set of problems we are interested in is of the form A_{\theta}x_{\theta}^{\star}=b_{\theta} (1) where A_{\theta}\in\mathbb{R}^{d\times d} is assumed to be invertible for each \theta\in\Theta , b_{\theta} is a right-hand-side vector that is given, and the objective is to recover x_{\theta}^{\star} . We will suppose that there is some externally supplied sequence of parameters (\theta_{i}) , i=1,2,\dots and index the systems according to A_{i}\equiv A_{\theta_{i}} (similarly x_{i}^{\star} , b_{i} ). Our task is then: given a sequence of data from previously solved linear systems, to use this data to accelerate solution of the system A_{n+1}x_{n+1}^{\star}=b_{n+1} . In this work we argue that this problem can be structured as regression problem and use the tools of Gaussian process regression to solve it. 1.1 Related Work In this work we will focus on iterative linear solvers to solve these related linear systems. Given the prevalence of related linear systems it is natural that there are many existing approaches that seek to solve this problem. These methods can roughly be split into the following three categories: Initial Guess Various attempts have been made to find improved initial guess for the iterative linear solver for subsequent problems while solving a series of linear systems. Warm restarting—using the solution of the previous linear system as the initial guess—is a commonly used approach. As an extension of this, extrapolating from previous solutions has also been explored (e.g., polynomial extrapolation in Shterev 2015 ; Austin et al. 2021 , using Taylor expansion in Clemens et al. 2003 , using weighted averages in Ye et al. 2020 ). Projection methods are also used ( Fischer 1998 ; Markovinović and Jansen 2006 ) to estimate an efficient initial guess. Though these attempts accelerate the linear solver to some extent, using a suitable preconditioner can provide a far greater acceleration. Preconditioning One efficient way of increasing the efficiency of the linear solver is by preconditioning. A commonly used strategy to obtain a good preconditioner for subsequent problems is to start with a general preconditioner and adapt it in some way based on the solution of previous systems ( Bergamaschi 2020 ; Li 2015 ; Carr et al. 2021 , e.g.) . Machine learning based approaches like graph neural networks are commonly used to for this purpose ( Häusner et al. 2024 ; Li et al. 2023 ) . Using covariances related to the problem as a preconditioner was also considered in Calvetti and Somersalo 2005 where a preconditioner for an ill-posed inverse problem is constructed as the covariance matrix of sampled solutions, interpreted as a random variable. The posterior covariance from a probabilistic linear solver with specific inverse prior has been used to accelerate generalized linear models in Tatzel et al. 2023 . Recycling Subspaces Another way of accelerating (Krylov-based) linear solvers is to recycle the Krylov subspaces explored for previous linear systems. The idea is to improve the search space for the current system by restricting it or enhancing it, leading to faster convergence. This is done by deflation ( Saad et al. 2000 ; de Roos and Hennig 2017 ; Daas et al. 2021 ) , augmentation ( Erhel and Guyomarc’h 2000 ; Carlberg et al. 2016 ) , or a combination of both. 1.2 Proposed Approach We propose to extend the framework of probabilistic linear solvers ( Hennig 2015 ; Cockayne et al. 2019 ) to build a solver for related linear systems. Existing probabilistic linear solvers typically function in a Bayesian framework by conditioning a prior distribution on observations of Eq. 1 (e.g. by left-multiplying by some matrix of search directions (S^{m})^{\top}\in\mathbb{R}^{m\times d} ). We propose to extend this approach by extending the prior over the parameter space \Theta , so that, after conditioning, we can use the posterior to extrapolate to other problems. We refer to this idea as using the probabilistic solver as a companion regression model for a classical iterative method. Specifically, we will use the posterior predictive mean as an initial guess for subsequent systems, and the posterior predictive covariance as the preconditioner for an iterative linear solver. 1.3 Structure of the Paper The paper proceeds as follows. In Section 2 we discuss the background on iterative solvers ( Section 2.1 ), probabilistic linear solvers ( Section 2.2 ) and vector-valued Gaussian processes ( Section 2.3 ). In Section 3 we use these tools to extend probabilistic linear solvers across a parameter space, and discuss how to utilise the posterior to accelerate subsequent solves. We provide some theoretical results in Section 4 and discuss efficient computation strategies in Section 5 . In Section 6 , we perform a simulation study ( Section 6.1 ) to demonstrate the advantages of our method, followed by an application on a Gaussian process hyperparameter optimisation problem in Section 6.2 . All the proofs are contained in Appendix A . Some practical implementation details and complexity analysis are discussed in Section B.1 and Section B.2 . Finally, some additional numerical results are presented in Appendix C . 2 Background In this section we will present the required background for the paper. We will primarily focus on solution of single linear systems, and will suppress dependence of this system on the parameter \theta to simplify the exposition. 2.1 Iterative Solvers Iterative linear solvers construct a sequence of iterates (x^{j}) which are such that x^{j}\to x^{\star} as j\to\infty . Well-known examples of such solvers are stationary iterative methods such as Richardson’s method; in such solvers the iterate x^{j+1} is constructed by applying an affine map to the previous iterate x^{j} . However such solvers are rarely used in contemporary applications, apart from occasionally to provide preconditioners (see e.g. Chen 2005 ); this is due to the fact that the reduction in error x^{j}-x^{\star} is typically rather slow, and that convergence is only guaranteed in the limit as j\to\infty . More sophisticated solvers such as Krylov methods (see e.g. Golub and Loan 2013 , Section 11.3 and Section 11.4) are more widely used in practice as a result of their faster convergence. This faster convergence is obtained because the map applied to x^{j} to obtain x^{j+1} is typically nonlinear rather than affine. As a result convergence is both faster and, for many methods, guaranteed after a finite number of iterations 1 1 1 These statements are true only in exact precision;