Solving Sparse Linear Systems Faster than Matrix Multiplication

We present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any value of matrix multiplication exponent 𝜔 > 2. This speedup holds for any input matrix 𝐴 with 𝑜(𝑛^{𝜔−1}/ log(𝜅(𝐴))) nonzeros, where 𝜅(𝐴) is the condition number of 𝐴. For poly(𝑛)-conditioned matrices with 𝑂(𝑛) ̃ nonzeros, and the current value of 𝜔, the bit complexity of our algorithm to solve to within any 1/poly(𝑛) error is 𝑂(𝑛^2.271). 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 an earlier algorithm for inverting matrices over finite fields. In our analysis of numerical stability, we use matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices and incorporate improved matrix anti-concentration bounds by Nie.