Numerical Linear Algebra in Linear Space

We present a randomized linear-space solver for general linear systems $\mathbf{A}\mathbf{x}=\mathbf{b}$ with $\mathbf{A}\in {\mathbb{Z}}^{n\times n}$ and $\mathbf{b}\in {\mathbb{Z}}^n$, without any assumption on the condition number of $\mathbf{A}$. For matrices whose entries are bounded by $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)$, the solver returns a $(1+\epsilon )$-multiplicative entry-wise approximation to vector $\mathbf{x}\in {\mathbb{Q}}^n$ using $\tilde{O}(n^2\cdot \mathrm{n}\mathrm{n}\mathrm{z}(\mathbf{A}))$ bit operations and $O(n\log n)$ bits of working space (i.e., linear in the size of a vector), where $\mathrm{n}\mathrm{n}\mathrm{z}$ denotes the number of nonzero entries. Our solver works for right-hand vector $\mathbf{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{n}\mathrm{n}\mathrm{z}(\mathbf{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.