Can linear systems be solved faster than matrix multiplication? Although there has been much progress on systems with additional structures, in the general setting, the complexity of solving an n × n linear system Ax = b is at least Ω (n ω) bit operations, where ω 2. This speedup holds for any input matrix A with o (n ω − 1 /log (κ (A) ) ) nonzeros, where κ (A) is the condition number of A. For poly (n) -conditioned matrices with \ (O (n) \) nonzeros, and the current value of ω, the bit complexity of our algorithm to solve to within any 1/poly (n) error is O (n 2. 331). 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 use matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices. Incorporating the matrix anti-concentration bounds by Nie STOC‘22 gives an improved bit complexity of O (n 2. 271).
Peng et al. (Mon,) studied this question.