Algebraformer: A Neural Approach to Linear Systems
Pietro Sittoni, Francesco Tudisco · 2025
Read Algebraformer: A Neural Approach to Linear Systems by Pietro Sittoni, Francesco Tudisco (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-2511-14263.txt.
Introduction
Pietro Sittoni and Francesco Tudisco teach a transformer net to solve sets of linear equations head-on. The classic solvers for ill-posed sets need care, tuning, or expert tricks to stay exact and stable. Their model, Algebraformer, learns the task end to end. A new code scheme lets it write down a matrix and a vector with memory that grows as the square of the size.
The model stays close to the true answer even when the set is badly ill-posed. Tests cover curve-fit tasks from spectral methods for edge-value problems and speed-ups for Newton steps. It matched the accuracy of classic tools at much lower cost in use, a hint that plain neural nets can take over parts of the old science-computing stack.
Catalog record
| CREATOR | Pietro Sittoni, Francesco Tudisco |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-14263
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Algebraformer: A Neural Approach to Linear Systems Pietro Sittoni, Francesco Tudisco Abstract Recent work in deep learning has opened new possibilities for solving classical algorithmic tasks using end-to-end learned models. In this work, we investigate the fundamental task of solving linear systems, particularly those that are ill-conditioned. Existing numerical methods for ill-conditioned systems often require careful parameter tuning, preconditioning, or domain-specific expertise to ensure accuracy and stability. In this work, we propose Algebraformer, a Transformer-based architecture that learns to solve linear systems end-to-end, even in the presence of severe ill-conditioning. Our model leverages a novel encoding scheme that enables efficient representation of matrix and vector inputs, with a memory complexity of 𝒪 ( n 2 ) \mathcal{O}(n^{2}) , supporting scalable inference. We demonstrate its effectiveness on application-driven linear problems, including interpolation tasks from spectral methods for boundary value problems and acceleration of the Newton method. Algebraformer achieves competitive accuracy with significantly lower computational overhead at test time, demonstrating that general-purpose neural architectures can effectively reduce complexity in traditional scientific computing pipelines. 1 Introduction Linear systems are ubiquitous in the physical sciences. Many fundamental tasks in physics, from solving inverse problems 29 to performing interpolation 46 , or from discretizing and simulating differential equations 10 ; 69 , ultimately reduce to solving a system of linear equations. Yet, while the theory behind linear solvers is well established, the practical numerical solution of ill-conditioned systems remains notoriously challenging. These systems are extremely sensitive to input perturbations and often lead to numerical instability, making their resolution highly dependent on problem-specific choices such as solver type, preconditioner design, and regularization strategy. As a result, even standard scientific computing libraries may yield poor results unless the system structure is explicitly accounted for and, in general, approaching these problems requires substantial expertise in numerical linear algebra, creating a barrier to accessible and robust solutions. Over the decades, three main classes of methods have been developed. Direct methods (LU, Cholesky, QR 16 ) are accurate but computationally prohibitive for large or sparse systems. Iterative solvers (Krylov methods 70 , Jacobi, Gauss-Seidel, SOR 58 ) scale better but require tuning and often fail under ill-conditioning. Randomized algorithms 49 ; 64 offer scalability but remain sensitive to conditioning. In all cases, the condition number is central, motivating preconditioning 13 ; 51 ; 3 ; 7 and regularization 67 ; 52 ; 17 ; 60 ; 26 ; 57 ; 8 ; 62 , which improve stability but demand careful design. In this work, we propose a new machine learning-based paradigm for solving linear systems that is simple, general, and effective even in the presence of severe ill-conditioning. Inspired by recent advances in machine learning, end-to-end solution for scientific computing, from solving PDEs 1 ; 6 to learning classical algorithms 72 ; 74 ; 77 , we introduce Algebraformer , a Transformer-based architecture 71 that can solve linear systems via a single forward pass. Overall, our main contributions are as follows : • We design a novel matrix encoding scheme that scales quadratically with the system size ( \mathcal{O}(n^{2}) memory), enabling Transformers to process linear systems of practical size; • We evaluate Algebraformer on a broad suite of problem instances, highlighting its robustness to ill-conditioning and noise, as well as its ability to quickly solve linear systems. • We demonstrate strong generalization across two use cases: spectral interpolation problems arising in solving boundary value problems and acceleration of the Newton method (we want to remark that the Newton method is widely used in physics, for example, in inverse problems 54 ; 59 ). In the BVP experiment, we further demonstrated the adaptability of Algebraformer to previously unseen equations. The model was first pre-trained on a diffusion equation and then fine-tuned on a more complex one, consistently outperforming a model trained from scratch. This highlights its ability to transfer relevant knowledge and effectively generalize to datasets outside its original training distribution. The experiment concerning the Newton method is provided in Appendix 6 . While we do not aim to outperform finely tuned, task-specific numerical methods, our goal is to provide a general-purpose, plug-and-play solver that offers a compelling trade-off between accuracy, robustness, and ease of use. By sidestepping the need for handcrafted solver pipelines and extensive tuning, Algebraformer reduces the entry barrier to solving challenging linear systems, opening the door to broader adoption of ML-based numerical solvers in scientific and engineering workflows. 2 Related Work Learning to accelerate numerical algorithms. There has been a surge of interest in learning-based approaches for improving classical solvers. Several works focus on accelerating iterative methods such as Conjugate Gradient for symmetric positive definite systems 42 ; 37 ; 81 , or GMRES-type solvers for specific applications like the Poisson equation 45 . Others focus on learned preconditioning strategies: neural networks have been used to construct preconditioners that speed up convergence 28 ; 48 ; 66 , or to optimize heuristics such as Jacobi and ILU variants 21 ; 63 . NeurKItt 47 , for example, employs a neural operator to predict the invariant subspace of the system matrix and accelerate solution convergence. However, these approaches are primarily designed to enhance classical numerical pipelines. In contrast, our work takes a fundamentally different perspective: we aim to learn an end-to-end solver that directly outputs the solution to a linear system, bypassing the traditional iterative or decomposition-based steps altogether. We leave for the appendix an extended related works section appendix A . 3 Method In this section, we present the design of Algebraformer, highlighting how matrices can be efficiently encoded into a sequence-to-sequence model that can be applied out of the box to solve a wide range of linear systems. 3.1 Algebraformer Transformers have become a cornerstone in many areas of machine learning, excelling at processing one-dimensional sequences of token embeddings. However, adapting them to handle inherently two-dimensional data poses significant challenges. In 12 , the authors address this by flattening a matrix of size n\times n into a sequence, representing each matrix entry with symbolic tokens. They explore various encoding schemes: P 10 , P 1000 , P 1999 , and FP 15 , which correspond to using 5, 3, 2, and 1 token(s) per matrix entry, respectively. While this approach is innovative and has inspired further research, it also comes with notable limitations. Most critically, the memory complexity of the self-attention mechanism scales as \mathcal{O}(n^{4}) , making it infeasible to train even on moderate-to-small matrices. Additionally, the symbolic encoding introduces significant computational overhead during inference. Finally, the method reduces numerical precision, capping accuracy at 10^{-2} , which may be inadequate for applications requiring finer resolution. Rather than flattening the matrix A\in\mathbb{R}^{n\times n} into a one-dimensional sequence of length n^{2} , we encode the matrix and vector inputs more efficiently. Specifically, we represent each column of A separately and associate it with the corresponding entry in the right-hand side vector b\in\mathbb{R}^{n} . The resulting input sequence consists of n tokens, where the i -th token is defined as [a_{i},b_{i}]\in\mathbb{R}^{n+1} , with a_{i} denoting the i -th column of A , and b_{i} the i -th component of b . This structured encoding enables the model to process the linear system in a format that preserves its