# Numerical Linear Algebra in Linear Space

arXiv: https://arxiv.org/abs/2507.02433 · HTML: https://mlsanity.com/paper/2507.02433/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Well-Conditioned Oblivious Perturbations in Linear Space](https://mlsanity.com/paper/2604.23193/) (2026)

## Abstract (arXiv)

We present a randomized linear-space solver for general linear systems A x = b with A ∈ mathbbZn × n and b ∈ mathbbZn, without any assumption on the condition number of A. For matrices whose entries are bounded by poly(n), the solver returns a (1+ε)-multiplicative entry-wise approximation to vector x ∈ mathbbQn using widetildeO(n2 · nnz(A)) bit operations and O(n log n) bits of working space (i.e., linear in the size of a vector), where nnz denotes the number of nonzero entries. Our solver works for right-hand vector b with entries up to nO(n). To our knowledge, this is the first linear-space linear system solver over the rationals that runs in widetildeO(n2 · nnz(A)) time. We also present several applications of our solver to numerical linear algebra problems, for which we provide algorithms with efficient polynomial running time and near-linear space. In particular, we present results for linear regression, linear programming, eigenvalues and eigenvectors, and singular value decomposition.