论文标题
求解稀疏线性系统比矩阵乘法更快
Solving Sparse Linear Systems Faster than Matrix Multiplication
论文作者
论文摘要
线性系统可以比矩阵乘法更快地求解吗？尽管对于图形结构化线性系统的特殊情况，在一般环境中取得了显着的进展，但求解$ n \ times n $线性系统的位复杂性$ ax = b $ as $ \ tilde {o}（n^ω）$，其中$ω<2.372864 $是矩阵倍增指数。即使对于具有多$（n）$条件编号的稀疏线性系统，对此进行改进也是一个空旷的问题。 在本文中，我们提出了一种算法，该算法在稀疏矩阵中求解线性系统比任何$ω> 2 $都比矩阵乘法快于矩阵乘法。对于任何输入矩阵$ a $ a $ o（n^{ω-1}/\ log（κ（a）））$ non-engeros，此加速度可容纳任何输入矩阵$ a $，其中$κ（a）$是$ a $的条件数。对于Poly $（n）$ - 带有$ \ tilde {o}（n）$ nonzeros的条件矩阵，以及$ω$的当前值，我们算法的位复杂性可以求解到任何$ 1/\ text {poly}（poly}（poly}（poly}（poly}）$ rorrive中， 我们的算法可以通过递归低位移级别化因素化为块Krylov方法的有效，随机实现。它的灵感来自[Eberly等人的算法。 ISSAC`06`07]用于在有限字段上倒置矩阵。在我们对数值稳定性的分析中，我们开发了矩阵抗浓缩技术，以结合半随机矩阵特征值中最小的特征值和最小的差距。
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 \times n$ linear system $Ax=b$ is $\tilde{O}(n^ω)$, where $ω< 2.372864$ is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with poly$(n)$ 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 $o(n^{ω-1}/\log(κ(A)))$ non-zeros, where $κ(A)$ is the condition number of $A$. For poly$(n)$-conditioned matrices with $\tilde{O}(n)$ nonzeros, and the current value of $ω$, the bit complexity of our algorithm to solve to within any $1/\text{poly}(n)$ error is $O(n^{2.331645})$. 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 anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices.
