CS Paper Radar

Numerical Stability of Linear Algebra Operations over Relational Databases

Andrei Draghici, Yuchen He, Dan Olteanu

cs.DB ·submitted 2026-09-12 08:28 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG math.NA ·2026-08-21 ·Victorita Dolean, Jemima Tabeart
code/data similarity 0.58
Abstract · 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 identi…

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.

0.42

Least-Squares and Low-Rank Approximation for Linear Relations Using a Diagrammatic Language

cs.SC math.NAmath.RA ·2026-08-24 ·Júlia de Araújo Mota, Iago Leal de Freitas, Lucas Rufino, João Paixão
theory similarity 0.56
Abstract · 47 pages

We employ the machinery of linear relations to the study of optimization problems in linear algebra. We first show that the relational version of the pseudo-inverse can be realized through a generalization of the least-squares problem. This allows one to prove that the pseudo-inverse realizes the solution of certain relational optimization problems. Our main result is showing that a certain truncation of this pseudo-inverse defines a solution to a relational version of the classical low-rank approximation problem which recovers both the Eckart-Young Theorem and several optimization problems involving pairs of matrices and vector spaces.

0.30

Convolution Sum-Product Queries

cs.DB ·2026-09-03 ·Kyle Deeds, Timo Camillo Merkl, Dan Suciu
similarity 0.54
Abstract

We study query evaluation for an extension of sum-product queries (SPQ) that allows atoms with linear combinations of variables (e.g. $A(2X+3Y-Z, Y+Z)$), which we call convolution sum-product queries (CSPQs). These queries arise in both practical settings (e.g. image processing workloads) and theoretical ones (e.g. the $(\min,+)$-convolution and $k$-SUM conjectures), and capture SPQs with added linear equality constraints. While prior work has considered the impact of linear in- and dis-equality constraints on query evaluation, the techniques developed in that setting are asymptotically sub-optimal for CSPQs. To address this, we describe several evaluation algorithms for CSPQs that leverage linear algebra techniques like rank analysis, quotient spaces, and variable substitution. First, we adapt Worst-Case Optimal Joins to CSPQs, achieving a runtime similar in spirit to that for conjunctive queries. Then, we extend the definition of tree decompositions (TDs) to CSPQs, and describe a factorized execution. In this extension, linear combinations are first-class citizens and play the same role as variables in traditional TDs. We define three width measures that bound the complexity of this execution with respect to the size of the domain values, of the active domain, and of the relation's support. Lastly, we show how these methods can be applied to arbitrary fields beyond the rationals.

0.24

Systematic Data Structure Lower Bounds via the Query-with-Sketch Model

cs.DS cs.CC ·2026-09-16 ·Sumegha Garg, Songhua He, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang
published similarity 0.54
Abstract · CCC 2026

We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix $\mathbf{M}\in\mathbb{R}^{n\times n}$ and parameters $k$ and $α$, the goal is to preprocess $\mathbf{M}$ so as to answer entry queries $(u,v)\mapsto \mathbf{M}^{k}[u,v]$ up to additive error $1/n^α$. We focus on AMP in the succinct and systematic regime, in which the data structure stores $\mathbf{M}$ verbatim, uses an additional $r$ bits of redundancy, and must answer queries by probing only a small number of entries of $\mathbf{M}$. Our main conceptual contribution is a general framework for proving probe--redundancy trade-offs for systematic data structures. We introduce the query-with-sketch model and develop a min-entropy-based approach that lifts conditional min-entropy bounds in the absence of redundancy to probe lower bounds in the presence of redundancy. We then establish these min-entropy bounds using problem-specific analytic and algebraic tools, for the downstream applications to AMP and its variants. As a consequence, our results provide new unconditional evidence toward a conjecture of Patrascu and Roditty (2010) on the space required for constant-time set-disjointness queries.

0.26

SAGE: A Unified Algebra and Self-Adaptive Execution for AI Functions in SQL

cs.AI ·2026-08-21 ·Xiangqi Wang
similarity 0.53
Abstract · arXiv admin comment: This version has been removed by arXiv administrators as the submitter did not have the rights to agree to the license …

SQL systems increasingly expose AI functions for tasks such as classification, extraction, filtering, ranking, retrieval, joining, and summarization. Despite their diverse APIs, these functions play only three relational roles: transforming individual rows, aggregating groups, or generating relationships between row pairs. We present SAGE (Self-Adaptive Generative Execution), a unified logical and physical framework that captures these roles with three typed primitives, AI_SCALAR, AI_AGG, and AI_JOIN, and composes them naturally with standard relational operators. All primitives share a confidence-gated execution interface while supporting physical strategies tailored to their relational shape. The main challenge is AI_JOIN, where SAGE analyzes the predicate, decomposes compound conditions when possible, and uses a recipe card together with a small label-free probe to select among complete execution strategies. Across a broad audit of public AI operators and evaluations spanning scalar, aggregate, and join workloads, this formulation covers common AI functionality while consistently improving execution quality and efficiency. SAGE achieves the strongest overall SemBench performance and, on a representative factorable join, reduces pairwise model calls by more than two orders of magnitude, yielding a 358-fold measured cost reduction.

0.08

Multiple-Function Approximated Coded Computing: Constructions and Error Bounds

cs.IT ·2026-10-12 ·Rimpi Borah, Wilton Kim, J. Harshan, Stanislav Kruglik, Han Mao Kiah
similarity 0.52
Abstract · 11 pages in two-column format. This updated version contains proofs of Theorem 1, Theorem 2 and Lemma 1 in Appendix

Coded computing mitigates stragglers in distributed computation. While Lagrange coded computing (LCC) enables exact polynomial computation over finite fields, Berrut approximated coded computing (BACC) enables approximate computation of arbitrary, including non-polynomial, functions in the analog domain. In applications such as multi-task learning and inference, multiple functions must be evaluated over different subsets of a common dataset, making single-round computation desirable to reduce communication overhead. An existing LCC approach addresses this requirement but is restricted to polynomial functions over finite fields, leaving single-round multi-function computation in the analog domain an open problem. In this work, we develop a single-round construction for computing multiple arbitrary functions using BACC. We first extend the existing multi-function computation approach in LCC to the BACC setting and derive an approximation-error bound. Building on this, we propose a construction based on Berrut basis functions for computing multiple arbitrary functions and derive its approximation-error bound. We analyze the scaling of both bounds with the number of functions and the number of data points per function, and numerically compare the two constructions over a wide range of arbitrary functions. The results demonstrate that the proposed construction achieves lower relative errors than the existing approach in the tested settings.

0.27

A Survey on the Use of Machine Learning within Computer Algebra

cs.SC cs.LG ·2026-11-17 ·Uzma Shafiq, Matthew England, Nayyar Zaidi
top venuesurveybenchmark similarity 0.52
Abstract · 31 pages

This survey explores the use of Machine Learning (ML) in the field of Computer Algebra (CA), both to optimise existing CA algorithms, and to perform symbolic computation directly. Traditional symbolic methods, while mathematically rigorous, often are computationally expensive thus limiting their use in real-world applications. Recent advances have shown that data-driven techniques can address these limitations by guiding heuristic decisions, selecting optimal algorithms, predicting structural properties of algebraic objects, or even making direct symbolic computations. We take a systematic literature review approach and uncover work in CA applications including cylindrical algebraic decomposition, Gröbner basis computation, symbolic integration, and many more. The survey compares the different ML approaches that have been employed for these tasks, ranging from decision trees to transformers. Issues uncovered by the survey include the lack of benchmark datasets for CA, which hinders the comparison of methods and the generalizability of ML models. The survey identifies the potential for explainable AI tools to help develop trust in decisions, and to drive forward CA research itself.

0.73

Tessera: Fast Join-Aggregates over Skewed Sparse Relations in Database Engines

cs.DB ·2026-10-29 ·Gyuyeong Kim
similarity 0.52
Abstract

Join-aggregate queries count or sum matching rows for each pair of values, often over skewed sparse relations in which a few values are frequent and most pairs of values never co-occur. Conventional execution plans materialize billions of intermediate join rows, taking minutes to tens of minutes per query. Recent matrix-based solutions reformulate these queries as matrix multiplication to reduce or avoid this materialization. However, they remain slow because they either store result cells for non-matching pairs or still materialize intermediate join rows for infrequent values. We present Tessera, a skew-aware join-aggregate operator for database engines that avoids both sources of overhead. Specifically, Tessera computes a sparse matrix product directly over the engine's rows, emits only nonzero cells as result rows, and prunes values that cannot meet the query's threshold before multiplication begins. It also offloads the dense block formed by pairs of the most frequent values to a CPU matrix accelerator when that block is dense enough. Experimental results show that Tessera is faster than the fastest existing system by 2.8x to 18.8x. In addition, Tessera outperforms DuckDB's execution plans by up to 1,802x.

0.19