Numerical Linear Algebra in Linear Space

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.