CS Paper Radar

Advanced Linear Algebra with Applications - Part I (Numerical linear algebra for PDEs, machine learning, and data assimilation)

Victorita Dolean, Jemima Tabeart

cs.LG math.NA ·submitted 2026-08-21 15:44 UTC · v2
code/data

Abstract

These lecture notes form the first part of a master's-level course on advanced numerical linear algebra. Their aim is not only to present the classical algorithms, but to show why the subject has become considerably more central than it was a generation ago. Numerical linear algebra grew up alongside the numerical solution of partial differential equations, and for a long time that is where its large sparse systems came from. Ranking the nodes of a network, assimilating observations into a weather forecast, and fitting a model to a large noisy data set now lead to problems of the same kind: too large to factorise, structured, and accessible only through matrix-vector products. Strikingly few ideas are needed for all of them. Each chapter therefore develops a standard topic and then puts it to work outside its original setting. We treat norms, factorisations, conditioning and floating-point arithmetic; sparse matrices arising from finite differences, from graphs and from machine learning; stationary iterations and the smoothing property; the conjugate gradient and Lanczos methods, with spectral clustering and regularisation by early stopping; Arnoldi and GMRES, with PageRank and large least squares; and finally preconditioning, Schwarz domain decomposition and multigrid. We assume a first course in linear algebra. Every section closes with a summary of what should be retained and every chapter with exercises, several drawn from past examinations. Accompanying Python code reproduces the numerical illustrations.

Comment
101 pages, 24 figures. Lecture notes; Part I of a two-part master's course. Generative AI (Claude Opus 5, Anthropic) was used to help identify seminal references, improve the language, and improve the graphical content; all statements, proofs, and references have been checked by the authors, who take full responsibility for the contents. Code: https://github.com/vicdolean/scicomp_examples

Closest papers

Nearest neighbours by meaning across the whole index.

The Numerical Linear Algebra of Large Language Models

cs.LG math.NA ·2026-10-03 ·Abdelkader Baggag, Yousef Saad
survey similarity 0.71
Abstract

Numerical Linear Algebra (NLA) has consistently played a vital role in advancing science by providing tools to solve fundamental problems encountered in scientific and engineering applications. Over the decades, it has continually evolved to meet the demands driven by successive waves of scientific discovery. For instance, during the 1950s and 1960s, substantial efforts were devoted to developing methods for solving eigenvalue problems that emerged from the rapidly growing field of aerodynamics. This led to the discovery of the LR and QR algorithms. Later the attention turned to the solution of sparse linear systems that were common in applications like computational aerodynamics. Today we are experiencing yet another wave of major scientific advancement and NLA is once more at the heart of its development. This Machine Learning (ML) wave is proving to be utterly disruptive in science and engineering. Many tools in ML particularly Large Language Models (LLMs) are grounded in matrix and tensor methods. As we are approaching Artificial General Intelligence (AGI), it is clear that matrix methods will be called to play an even more significant role. For the numerical linear practitioner the speed of the current change makes it particularly challenging to adapt. This is a survey article that centers on machine learning techniques, with a particular focus on large language models. It has two main objectives. The first is to clarify the core concepts behind Large Language Models in a manner accessible to specialists in numerical methods. The second is to examine the key Numerical Linear Algebra concepts employed by LLM techniques, while also highlighting several significant recent contributions of NLA to the field.

0.27

An overview of machine learning-enhanced iterative methods for systems of linear and nonlinear equations

cs.LG math.NA ·2026-10-05 ·Yuhuang Meng, Jing Zhao, Alexander Heinlein
top venuesurvey similarity 0.62
Abstract · 78 pages

Systems of equations arise in a wide range of scientific and engineering applications. The present work focuses on solvers for general systems of equations, including but not limited to those arising from partial differential equations. These systems can be broadly categorized into linear and nonlinear problems. For large linear systems, iterative solvers are generally preferred over direct methods due to the latter's superlinear growth of computational costs. Although convergence theory is well-developed under certain assumptions on the coefficient matrix, many classes of systems still pose open challenges. These difficulties become even more severe for systems of nonlinear equations, where nonlinear solvers typically rely on repeated linearization. For example, Newton's method may even converge quadratically near the solution; it can also converge slowly or diverge when the initial guess is not chosen appropriately. A wide range of solvers with diverse variants and hyperparameter settings exists, and the development of efficient and robust iterative methods remains an active area of research. Recently, machine learning (ML) techniques have been applied to enhance the efficiency of classical iterative methods while preserving their interpretability and reliability. We refer to these ML-enhanced iterative methods as hybrid iterative methods, in the sense that they combine classical iterative methods with ML. This paper provides a comprehensive overview of state-of-the-art approaches to constructing hybrid iterative methods for systems of both linear and nonlinear equations, while also discussing open challenges and outlining potential directions for future research.

0.67

Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure

cs.LG stat.ML ·2026-08-21 ·Lawrence K. Saul, Ningyuan Huang, Dennis Bollweg, Jeff Soules, Diana C. Halikias
similarity 0.60
Abstract

We investigate when a sparse nonnegative matrix can be recovered from a real-valued matrix of much lower rank by zeroing out its negative elements. The potential for such decompositions suggests a mathematical connection between sparsity and rank; we analyze a number of sparse matrices with this latent low-rank structure and use them to illustrate the geometric origins of this connection. Previous algorithms have discovered these decompositions via an alternating minimization over the factors of a low-rank matrix, but to do so, they have also needed to compute and store another matrix, neither sparse nor low-rank, that is the size of their product. We develop a stochastic, alternating least-squares algorithm that operates on smaller blocks of this dense matrix and scales as a result to much larger problems. We also show how to further accelerate this algorithm with sparse optimizations and customized CUDA kernels. As one example, we use the algorithm to analyze the sparse matrix of synaptic weights for the recently published $\textit{Drosphilia}$ connectome. The nonzero elements of this matrix, with 139,255 rows and columns, record the number of synapses between cells in the nervous system of a female fruit fly. Despite a slowly decaying spectrum of singular values, this matrix exhibits a latent low-rank structure that is predictive of cell categories across multiple levels of specificity.

0.38

A single LU~factorization approach to model reduction for linear system families with a quadratic matrix pencil

cs.CE math.NAphysics.comp-ph ·2026-10-10 ·Mikhail A. Botchev, Leonid Knizhnerman, Nikolai L. Zamarashkin, Dmitry A. Zheltkov
similarity 0.60
Abstract · 21 pages, 11 figures, 3 tables

To solve a family of large linear systems where the system matrix depends on the family parameter quadratically, we propose a new solution approach. Our method employs the derivatives of solutions with respect to the parameter. It turns out that the accumulated solution derivatives of increasing order, evaluated at a single specially chosen parameter value, provide successively better approximations to solution subspaces for the whole linear system family. We show that the derivatives can be computed by a recurrence, involving, at each step, solving a linear system with the same matrix. Constructing an orthonormal basis for the subspace spanned by the derivatives then leads to an efficient solver where just a single (sparse) LU factorization (or a single preconditioner setup in an iterative scheme) suffices to solve the whole linear system family. We call the new method ODB (orthonormal derivative basis method). As shown in numerical tests, compared to conventional solution methods, the ODB method allows to drastically reduce computational costs.

0.28

Numerical Stability of Linear Algebra Operations over Relational Databases

cs.DB ·2026-09-12 ·Andrei Draghici, Yuchen He, Dan Olteanu
similarity 0.58
Abstract

A large body of work in the database literature develops efficient algorithms for linear algebra and machine learning over matrices defined by relational joins, yet the numerical stability of such computations has so far received no attention. This is a practical concern: a join matrix can be much larger than the input database, and the repeated copies of input values it contains compound the floating-point errors incurred by the numerical operations performed over it. This paper initiates a formal investigation of numerical stability for linear algebra over database joins. We first show that backward stability, the standard yardstick of numerical stability, loses its effectiveness in this setting: join matrices form a structured subspace of the ambient matrix space, so a perturbation explaining a computed result need not correspond to any perturbed input database. This failure already occurs for operations as simple as matrix-vector multiplication. To overcome this limitation, we introduce projected backward stability, a generalization of backward stability from the computation of one function to that of a composition of two functions, and establish its connection to classical backward stability. In our database setting, the two functions are the join query and the numerical operation. We further introduce the database condition number as the square root of the ratio of maximal to minimal number of copies of input data values into the join matrix, and show that it quantifies how a perturbation of the join matrix is amplified into a perturbation of the input database, independently of the computation used. The database condition number coincides with the classical condition number of the expansion matrix that replicates input values into the join matrix.

0.24

Sparse Orthogonal Regression Technique: A Spectral Framework for Equation Discovery, Approximation, and Integration

cs.LG ·2026-08-13 ·Sabin Roman, Ljupco Todorovski, Saso Dzeroski
published similarity 0.57
Abstract · 15 pages, 4 figures. Accepted for oral presentation at the 29th International Conference on Discovery Science (DS 2026), Mainz, Germany, Oct…

We develop the Sparse Orthogonal Regression Technique (SORT), a sparse spectral framework for learning orthonormal-basis expansions from noisy and irregularly sampled data. SORT estimates expansion coefficients directly from observations using L1-regularized regression, avoiding explicit quadrature or analytic inner-product evaluation. The central application is data-driven discovery of ordinary differential equations: vector fields are represented in chosen orthogonal bases and learned as sparse coefficient expansions. This provides a complementary route to symbolic regression, grammar-based discovery, and SINDy-style sparse identification by first recovering a compact spectral representation, which can later guide searches for simpler analytic forms. Across the dynamical-system experiments, SORT matches or improves upon library-based sparse-regression baselines when the basis is well adapted to the problem, and shows more stable degradation under sparse sampling, noisy derivative estimates, and representation mismatch. Specific examples illustrate why this representation is useful: if a finite library misses the problem-specific nonlinearity, the resulting model can fail. SORT is not immune to mismatch, but it shifts the problem away from brittle selection among generic terms to basis design adapted to the problem domain. The experiments also show that dominant low-order coefficients persist as model order increases, supporting order-consistent model growth. Beyond equation discovery, the same learned expansion supports nonlinear approximation and estimation of complex, high-dimensional integrals by coefficient readout. Overall, SORT provides a reusable intermediate representation for system identification, approximation, and integration, while making basis design an explicit part of the scientific modeling problem.

0.28

Newton's Method for CP Decomposition

cs.MS ·2026-11-16 ·DuBose Tuller, Grey Ballard, Hussam Al Daas, Nicholas I. M. Gould
similarity 0.57
Abstract · 30 pages, 7 figures

We present an algorithm for computing the CP tensor decomposition using Newton's method. The problem of fitting a CP model to a data tensor with least squares loss can be solved by various gradient-based optimization techniques, including Gauss-Newton methods that exploit the tensor structure of the problem and iteratively solve the linear system involving the approximate Hessian matrix to determine the step direction at each iteration. Gauss-Newton methods exhibit superlinear convergence when the residual is small but can otherwise struggle to converge when the approximation to the Hessian is not accurate. We show that the Gauss-Newton approach can be extended to Newton's method, using the true Hessian to obtain fast convergence even in the case of large residuals. In particular, we derive efficient means of applying the true Hessian to vectors for use within an iterative solver, we employ globalization and regularization techniques to make the Newton model robust to ill-conditioned and/or indefinite Hessians, and we propose hybrid use of Gauss-Newton and Newton steps to balance convergence behavior both far and near local minima. Our numerical experiments use synthetic examples to show in which scenarios Gauss-Newton and other methods struggle to converge, and we demonstrate the superiority of the hybrid approach on two application data sets.

0.34

A Transformer-Derived Iterative Preconditioner

cs.LG ·2026-11-17 ·Patrick Lutz, Themistoklis Haris, Aditya Gangrade, Venkatesh Saligrama
top venuetheory similarity 0.57
Abstract · Accepted at NeurIPS 2026

Transformers trained on in-context prediction problems can learn known numerical algorithms, e.g., gradient descent. We go further, showing that their internal computations can reveal new algorithms with provable guarantees. A softmax-attention transformer trained to solve linear systems $Xw=y$ implicitly improves matrix conditioning. Tracing $XX^\top$ reveals an iterative preconditioning primitive, which we develop into RAPID, a standalone algorithm requiring no learned components. RAPID is an anytime preconditioner for symmetric positive definite (SPD) matrices, using randomized mixing and sparse local corrections to improve conditioning. Proof-of-concept experiments on synthetic and real-world problems consistently improve conditioning and reduce conjugate gradient iterations needed to reach a target accuracy. For a Haar-mixing idealization, we prove convergence to any fixed target condition number regardless of spectral distribution, with only logarithmic dependence on initial conditioning. Together, these results show how a transformer can discover a broadly applicable numerical algorithm.

0.31