.png){kind=icon}
.png){kind=icon}
Return
Solving Sparse Linear Systems Faster than Matrix Multiplication
.png){kind=icon}
PRE
AI
DOI：10.1145/3767721.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 x n linear system Ax = b is at least Omega(n(omega) ) bit operations, where omega < 2.372 is the matrix multiplication exponent. Improving on this bound of n omega has been an open problem even for sparse linear systems with poly(n) condition number. In this article, we present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication or any omega > 2. This speedup holds for any input matrix A with o(n(omega-1)/ log(kappa(A))) nonzeros, where kappa(A) is the condition number of A. For poly(n)-conditioned matrices with O (n) nonzeros, and the current value of omega, 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))
Keywords:
Linear systems
matrix anti-concentration
krylov spaces
structured matrices
Journal
J
IF:
2.5
Papers:
20
Citations:
0