2025/07/03 by Liu, Yiping, Nguyen, Hoai-An, Yang, Junzhao
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.02433
We present a randomized linear-space solver for general linear systems A x = b with A ∈ ℤn × n and b ∈ ℤn, 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 ∈ ℚn 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.