以比矩阵乘法更快的速度求解稀疏线性方程组

《Journal of the ACM》：Solving Sparse Linear Systems Faster than Matrix Multiplication

高效求解稀疏线性系统的算法及其复杂度分析。提出基于块Krylov方法和递归低位移秩分解的随机算法，对条件数多项式次且非零元为o(n^{ω?1}/logκ(A))的稀疏矩阵，求解误差在1/poly(n)内的复杂度为O(n^{2.331})，结合矩阵反浓度技术优化后达到O(n^{2.271})，突破传统矩阵乘法复杂度下限。

　　

摘要

线性系统的求解速度能否快于矩阵乘法？尽管在具有额外结构的系统上已经取得了很多进展，但在一般情况下，求解一个 n × n 线性系统 Ax = b 的复杂度至少为 Ω(n^ω) 比特运算量，其中 ω < 2.372 是矩阵乘法的指数。即使对于条件数为 poly(n) 的稀疏线性系统，改进这一 n^ω 的界限仍然是一个未解决的问题。

在本文中，我们提出了一种算法，该算法求解稀疏矩阵中的线性系统的速度渐进地快于矩阵乘法或任何大于 2 的 ω 值。这种加速效果适用于任何具有 o(n^{ω ? 1}/log?(κ(A))) 个非零元素的输入矩阵 A，其中 κ(A) 是矩阵 A 的条件数。对于条件数为 poly(n) 的矩阵（具有 $\tilde{O}(\mathrm{n<mo>)</mo>}$ 个非零元素的情况，我们的算法在 1/poly(n) 的误差范围内求解的比特复杂度为 O(n^2.331)。

我们的算法可以被视为一种高效的、基于递归低位移秩分解的块 Krylov 方法的实现。它的灵感来源于 [Eberly 等人在 ISSAC ‘06 ‘07] 会议上提出的有限域上矩阵求逆的算法。在分析数值稳定性时，我们使用了矩阵反集中技术来限定半随机矩阵的最小特征值和特征值之间的最小间隙。结合 [Nie STOC‘22] 提出的矩阵反集中界限，使得算法的比特复杂度进一步提高到 O(n^2.271)。