Numerical Linear Algebra in Linear Space

We present a randomized linear-space solver for general linear systems $\textbf A\text x=\textbf b$ with $\textbf A \in \mathbb{Z}^{n \times n}$ and $\textbf b \in \mathbb{Z}^n$, without any assumption on the condition number of $\textbf A$. For matrices whose entries are bounded by $\mathrm{poly}(n)$, the solver returns a $(1+\epsilon)$-multiplicative entry-wise approximation to vector $\text x \in \mathbb{Q}^n$ using $\tilde O(n^2 \cdot \mathrm{nnz}(\textbf A))$ bit operations and $O(n \log n)$ bits of working space (i.e., linear in the size of a vector), where $\mathrm{nnz}$ denotes the number of nonzero entries. Our solver works for right-hand vector $\textbf b$ with entries up to $n^{O(n)}$. To our knowledge, this is the first linear-space linear system solver over the rationals that runs in $\tilde O(n^2 \cdot \mathrm{nnz}(\textbf 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.