引用e79 · 2021-03
“a link to the paper discussed in the article for anyone who is curious:”
给出文章所讨论论文的链接,供感兴趣的人阅读
稀疏线性系统的求解首次渐近快于矩阵乘法
一般情形下 n×n 线性系统 Ax=b 的比特复杂度为 Õ(n^ω),其中 ω 为矩阵乘法指数;即使对条件数为 poly(n) 的稀疏系统,能否超越它也一直是公开问题。论文给出一种算法,对任意 ω>2,在稀疏矩阵上求解线性系统都渐近快于矩阵乘法,要求非零元个数为 o(n^(ω-1)/log κ(A))。对条件数 poly(n)、非零元为 Õ(n) 的矩阵,按当前 ω 的取值,求解到任意 1/poly(n) 误差的比特复杂度为 O(n^2.331645)。该算法可看作用递归低位移秩分解对分块 Krylov 方法的高效随机化实现,数值稳定性分析中发展了矩阵反集中技术。
HN 评论者把它作为文章所讨论论文的原文链接,主题是稀疏线性方程组求解比矩阵乘法更快。
“a link to the paper discussed in the article for anyone who is curious:”