Solving Sparse Linear Systems Faster than Matrix Multiplication
Solving Sparse Linear Systems Faster than Matrix Multiplication
复制标题
比矩阵乘法更快地求解稀疏线性系统
DOI：
10.1137/1.9781611976465.31
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Vempala, Santosh S.
中科院分区：
文献类型：
--
作者：
Peng, Richard;Vempala, Santosh S.
线性系统的求解速度能比矩阵乘法更快吗？虽然图结构线性系统的特殊情况已经取得了显着的进展，但在一般情况下，求解 ann×n 线性系统Ax=bisÕ(nω) 的位复杂度，其中ω< 2.372864 是矩阵乘法指数。即使对于具有 Poly(n) 条件数的稀疏线性系统，对此进行改进也是一个悬而未决的问题。在本文中，我们提出了一种算法，该算法在求解稀疏矩阵中的线性系统时，渐进地比任何 ω> 2 的矩阵乘法更快。这种加速适用于任何输入矩阵 Awitho(nω–1/log(κ(A))) 非零，其中 κ(A) 是 A 的条件数。对于具有 Õ(n) 非零值和 ω 当前值的 Poly(n) 条件矩阵，我们的算法在任何 1/poly(n) 误差范围内求解的位复杂度为 O(n2.331645)。我们的算法可以被视为通过递归低位移秩分解的块 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 ann×nlinear systemAx=bisÕ(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 matrixAwitho(nω–1/log(κ(A))) non-zeros, whereκ(A) is the condition number ofA. For poly(n)-conditioned matrices withÕ(n) nonzeros, and the current value ofω, the bit complexity of our algorithm to solve to within any 1/poly(n) error isO(n2.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.
登录
查看更多内容
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
M. G. Bruin
通讯作者：
M. G. Bruin
随机矩阵：特征值之间间隙的尾部边界
影响因子：
2
作者：
H. Nguyen;T. Tao;V. Vu
通讯作者：
V. Vu
稀疏随机矩阵具有简单谱
DOI：
10.1214/19-aihp1032
发表时间：
2020
期刊：
Probabilités et Statistiques
影响因子：
--
作者：
Luh, Kyle;Vu, Van
通讯作者：
Vu, Van
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
D. Spielman;N. Srivastava
通讯作者：
N. Srivastava
平衡分离器的指数逼近、lanczos 方法和 Õ(m) 时间谱算法
DOI：
--
发表时间：
2011
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
L. Orecchia;Sushant Sachdeva;Nisheeth K. Vishnoi
通讯作者：
Nisheeth K. Vishnoi