Solving Sparse Linear Systems Faster than Matrix Multiplication

Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph structured linear systems, in the general setting, the bit complexity of solving an n ˆn linear system Ax " b is Õpn ω q, where ω ă 2.372864 is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with polypnq condition number.

In this paper, we present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any ω ą 2. This speedup holds for any input matrix A with opn ω´1 logpκpAqqq non-zeros, where κpAq is the condition number of A. For polypnq-conditioned matrices with Õpnq nonzeros, and the current value of ω, the bit complexity of our algorithm to solve to within any 1polypnq error is Opn 2.331645 q.

Our algorithm can be viewed as an efficient, randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly et al. ISSAC '06 '07] for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anticoncentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices. 1 We will be measuring bit-complexity under fixed-point arithmetic. Here the machine word size is on the order of the maximum number of digits of precision in A, and the total cost is measured by the number of word operations. The need to account for bit-complexity of the numbers naturally led to the notion of condition number [Tur48,Blu04]. The logarithm of the condition number measures the additional number of words needed to store A ´1 (and thus A ´1b) compared to A. In particular, matrices with polypnq condition number can be stored with a constant factor overhead in precision, and are numerically stable under standard floating point number representations.