Truly linear working space and the bit-time frontier for rational linear-system solvers with entrywise multiplicative guarantees

The central primitive of exact numerical linear algebra — solving $\mathbf{A}\mathbf{x}=\mathbf{b}$ for an integer matrix $\mathbf{A}$ with certified accuracy — does not yet have a determined optimal working-space complexity. Liu, Nguyen, and Yang (2025) gave the first polynomial-time rational solver with near-linear working space: with no assumption on the condition number, it returns a $(1+\varepsilon)$-multiplicative entrywise approximation of $\mathbf{A}^{-1}\mathbf{b}$ using $\widetilde{O}(n^2\cdot\mathrm{nnz}(\mathbf{A}))$ bit operations and $O(n\log(nU))$ bits of working space, where $U$ bounds the entries of $\mathbf{A}$. The paper explicitly leaves open whether truly linear space — $O(n\log U)$ bits, or even $O(n)$ bits — is achievable in polynomial time (the crux being 0/1 matrices, where the current bound carries an extra $\Theta(\log n)$ factor), and whether the $\widetilde{O}(n^2\cdot\mathrm{nnz})$ bit-time can be improved toward Wiedemann's $\widetilde{O}(n\cdot\mathrm{nnz})$ finite-field runtime while staying in linear space. The problem is open: an algorithm or a lower bound resolves each component.

Background

Exact linear algebra over the integers asks for solutions of $\mathbf{A}\mathbf{x}=\mathbf{b}$ with $\mathbf{A}\in\mathbb{Z}^{n\times n}$ carried to certified accuracy, and it measures cost at the bit level: time in bit operations and memory in bits. In the model used by the source paper — a random-access machine with read-only input — the working space is the number of bits of memory beyond the read-only input (which cannot be modified) and beyond output that has already been written; the matrix $\mathbf{A}$ is not stored but accessed as a black box that computes matrix-vector products $\mathbf{A}\mathbf{v}$. Working space counted this way can be far smaller than the input or the output.

The output guarantee studied here is a $(1+\varepsilon)$-multiplicative entrywise approximation: each output entry $\hat{x}_i$ must lie within a factor $1\pm\varepsilon$ of the exact rational entry $x_i=(\mathbf{A}^{-1}\mathbf{b})_i$. This is stronger than the norm-wise approximations $\|\hat{\mathbf{x}}-\mathbf{x}\|\leq\varepsilon\|\mathbf{x}\|$ usual in numerical analysis, because individual entries of $\mathbf{A}^{-1}\mathbf{b}$ can be exponentially small or exponentially large even for benign integer matrices; moreover it is demanded without any bound on the condition number $\kappa(\mathbf{A})$ (the ratio of the matrix's largest to smallest singular value, i.e. its worst-case stretching factor), which most fast solvers assume is at most polynomial in $n$. Since entries of $\mathbf{A}^{-1}\mathbf{b}$ can be as large as $2^{\Theta(n)}$, the output is written incrementally as $O(\log(nU/\varepsilon))$-bit floating-point numbers, where $U$ bounds $|\mathbf{A}_{ij}|$ and $\mathrm{nnz}(\mathbf{A})$ is the number of nonzero entries.

Two classical techniques underlie exact rational solving. Wiedemann's black-box method solves a sparse system over a finite field $\mathbb{Z}_p$ in $\widetilde{O}(n\cdot\mathrm{nnz}(\mathbf{A}))$ field operations by recovering the minimal polynomial (the lowest-degree annihilating polynomial) of the Krylov sequence $\mathbf{v},\mathbf{A}\mathbf{v},\mathbf{A}^2\mathbf{v},\dots$, using the Berlekamp–Massey algorithm, which finds the shortest linear recurrence satisfied by a scalar sequence. Dixon's p-adic lifting solves the system modulo a small prime and lifts the solution to growing p-adic precision; rational reconstruction then recovers the exact rational answer from its residues modulo enough coprime primes (Chinese remaindering plus a gcd-based step). By Cramer's rule each solution entry is a ratio of determinants, and determinants of even 0/1 matrices have bit-length $\Theta(n\log n)$, so reconstruction needs a modulus of about $n\log(nU)$ bits — the source paper notes this is the minimal requirement for rational reconstruction. Classical combinations of these techniques reach roughly $\widetilde{O}(n^2\cdot\mathrm{nnz})$ time but use $\Theta(n^2)$ (or at best $\Theta(n^{1.5})$) words of working storage; the source paper also records folklore combinations achieving $O(n)$ space at roughly $\widetilde{O}(n^4)$ time for sparse matrices.

Liu, Nguyen, and Yang (2025) gave the first polynomial-time rational solver with near-linear working space: for invertible $\mathbf{A}$ with entries in $[-U,U]$ and $\mathbf{b}$ with entries up to $U^n$, it outputs a $(1+\varepsilon)$-multiplicative entrywise approximation with high probability using $\widetilde{O}(n^2\log(1/\varepsilon)\cdot\mathrm{nnz}(\mathbf{A}))$ bit operations and $O(n\log(nU))$ bits of working space, with no condition-number assumption; at extreme precision it returns exact solutions in the same space, and it yields near-linear-space polynomial-time algorithms for linear regression, linear programming, eigenvalues and eigenvectors, and the singular value decomposition.

What remains open is the last logarithmic factor in space and the quadratic-in-$n$ time overhead. For $U=\mathrm{poly}(n)$ the bound $O(n\log(nU))$ is linear in the usual word sense; the crux is small $U$: for a 0/1 matrix, every column of which fits in $O(n)$ bits, the solver still uses $O(n\log n)$ bits. The authors state that achieving truly linear space — $O(n\log U)$ or $O(n)$ bits — at polynomial time is open, and that finite-field methods appear fundamentally incapable of it. They also decline to pursue sublinear space: a solver in $O(n^{0.99})$ bits with multiplicative guarantees would yield a polynomial-time, $O(n^{0.99})$-space algorithm for directed s-t connectivity in graphs, a longstanding open problem in space-bounded computation. On the time side they observe that even for sparse matrices with polynomially-bounded condition number, a $\widetilde{O}(n^2)$-time solver in linear space would be a major open problem, and that matching Wiedemann's $\widetilde{O}(n\cdot\mathrm{nnz})$ runtime over the rationals may be out of reach; reductions showing that general linear-system solving over $\mathbb{Z}_p$ embeds into unit-weight graph Laplacians (the Laplacian matrices of unweighted graphs) with only polylogarithmic overhead (Chen–Gao–Huang–Peng–Wang) reinforce this pessimism for structured fast solvers.

Problem Statement

Work in the computational model of the source paper: a RAM with read-only input, where time is measured in bit operations and working space in bits, excluding the read-only input and any output already written; the matrix $\mathbf{A}$ is accessed only as a black box computing matrix-vector products. The input is an invertible $\mathbf{A}\in\mathbb{Z}^{n\times n}$ with entries in $[-U,U]$ and $\mathbf{b}\in\mathbb{Z}^n$ with entries in $[-U^n,U^n]$; the required output is a $(1+\varepsilon)$-multiplicative entrywise approximation of $\mathbf{x}=\mathbf{A}^{-1}\mathbf{b}$ (each entry within factor $1\pm\varepsilon$), with no assumption on the condition number of $\mathbf{A}$.

The established bound (Liu–Nguyen–Yang 2025) is $\widetilde{O}(n^2\log(1/\varepsilon)\cdot\mathrm{nnz}(\mathbf{A}))$ bit operations and $O(n\log(nU))$ bits of working space. Two linked questions define the open frontier, with the common objective of determining the time-space complexity of this task:

(1) Space optimality. Does a polynomial-time (in $n$, $\log U$, $\log(1/\varepsilon)$) randomized algorithm with the above output guarantee exist that uses truly linear working space — $O(n\log U)$ bits, or even $O(n)$ bits? The question is sharpest for $U=O(1)$ (e.g. 0/1 matrices), where it asks whether the extra $\Theta(\log n)$ factor in the current bound can be removed. A negative answer — an unconditional proof that $\Omega(n\log(nU))$ bits of working space are necessary for any bounded-error algorithm in this model — equally resolves this component.

(2) Time within linear space. Can the $\widetilde{O}(n^2\cdot\mathrm{nnz}(\mathbf{A}))$ bit-operation bound be improved while keeping (near-)linear working space — in particular, matching Wiedemann's $\widetilde{O}(n\cdot\mathrm{nnz})$ finite-field runtime in the rational setting, or achieving $\widetilde{O}(n^2)$ bit time for sparse matrices even under a polynomial condition-number bound? The source paper states that this last target alone is a major open problem. Any asymptotic improvement of the $\widetilde{O}(n^2\cdot\mathrm{nnz}(\mathbf{A}))$ bit-operation bound within (near-)linear working space, with the entrywise guarantee above, resolves this component, the two named targets being the most significant such improvements.

Each component is resolved by an algorithm or by a lower bound. Known barriers that any answer must respect or overturn: finite-field rational reconstruction of a single entry needs a modulus of $\Theta(n\log(nU))$ bits; a determinant of a 0/1 matrix requires $\Omega(n\log n)$ bits to store; and a solver with $O(n^{0.99})$ bits of working space and multiplicative guarantees would imply a polynomial-time, $O(n^{0.99})$-space algorithm for directed s-t connectivity, which is itself open.

References

1. Yiping Liu, Hoai-An Nguyen, Junzhao Yang. Numerical Linear Algebra in Linear Space. arXiv:2507.02433 (2025). DOI: 10.48550/arxiv.2507.02433. https://arxiv.org/abs/2507.02433
2. Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong, Mark Rudelson. Well-Conditioned Oblivious Perturbations in Linear Space. arXiv:2604.23193 (2026). DOI: 10.48550/arxiv.2604.23193. https://arxiv.org/abs/2604.23193
3. John D. Dixon. Exact solution of linear equations using P-adic expansions. Numerische Mathematik 40:137–141 (1982). DOI: 10.1007/BF01459082. https://doi.org/10.1007/BF01459082
4. D. Wiedemann. Solving sparse linear equations over finite fields. IEEE Transactions on Information Theory 32(1):54–62 (1986). DOI: 10.1109/TIT.1986.1057137. https://doi.org/10.1109/TIT.1986.1057137
5. Mehrdad Ghadiri, Hoai-An Nguyen, Junzhao Yang. Entrywise Approximation for Matrix Inversion and Linear Systems. arXiv:2504.19054 (2025, revised October 2025). DOI: 10.48550/arxiv.2504.19054. https://arxiv.org/abs/2504.19054
6. Jingbang Chen, Mehrdad Ghadiri, Hoai-An Nguyen, Richard Peng, Junzhao Yang. Entrywise Approximate Laplacian Solving. arXiv:2409.10022 (2024). DOI: 10.48550/arxiv.2409.10022. https://arxiv.org/abs/2409.10022
7. Jingbang Chen, Yu Gao, Yufan Huang, Richard Peng, Runze Wang. Hardness of Graph-Structured Algebraic and Symbolic Problems. arXiv:2109.12736 (2021, revised November 2022). DOI: 10.48550/arxiv.2109.12736. https://arxiv.org/abs/2109.12736
8. Yang P. Liu, Hoai-An Nguyen, Noah G. Singer, David P. Woodruff. Streaming Complexity Separations for Dense and Sparse Graphs. arXiv:2605.09814 (2026). DOI: 10.48550/arxiv.2605.09814. https://arxiv.org/abs/2605.09814