.png){kind=icon}
返回
Solving Sparse Linear Systems Faster than Matrix Multiplication
.png){kind=icon}
PRE
AI
DOI：10.1145/3767721.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
线性方程组能否比矩阵乘法更快求解？尽管在具有额外结构的系统中已有很大进展，但在一般情形下，求解n×n线性方程组Ax=b的复杂度至少为Ω(n^ω)次位运算，其中ω<2.372为矩阵乘法指数。即使对于条件数为多项式级的稀疏线性系统，改进这一n^ω界也是一个公开问题。本文提出了一种算法，可在稀疏矩阵上渐近地以快于矩阵乘法或任何ω>2的速度求解线性方程组。该加速适用于任何非零元素数量为o(n^(ω-1)/log(κ(A)))的输入矩阵A，其中κ(A)为矩阵A的条件数。对于具有O(n)非零元素且条件数为多项式级的矩阵，在当前ω值下，本算法将解误差控制在1/poly(n)以内的位复杂度为O(n^2.331)。本算法可视为通过递归低位移秩分解实现的块Krylov方法的高效随机化实现。其灵感来源于[Eberly et al. ISSAC '06 '07]提出的有限域上矩阵求逆算法。在数值稳定性分析中，我们采用矩阵反集中技术来界定半随机矩阵的最小特征值及特征值的最小间隙。通过纳入[Nie STOC'22]提出的矩阵反集中界，可将位复杂度改进为O(n^2.271)。
Keyword:
Linear systems
matrix anti-concentration
krylov spaces
structured matrices
期刊
J
IF:
2.5
论文数:
20
被引数:
0
机构
引用论文
.png){kind=icon}
查看更多内容