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.