按年被提到
20202021 · 3 次2026
算法与数据结构›经典算法与数据结构·arXiv:2007.10254 · cs.DS

Solving Sparse Linear Systems Faster than Matrix Multiplication

比矩阵乘法更快地求解稀疏线性方程组
Richard Peng, Santosh Vempala · 2020

稀疏线性系统的求解首次渐近快于矩阵乘法

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2021-03-09 · 最近 2021-08-29发表于 Society for Industrial and Applied Mathematics eBooks
3不同的人
3活跃月份
3讨论串
33被引(OpenAlex)

一般情形下 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 为什么提它

HN 评论者把它作为文章所讨论论文的原文链接,主题是稀疏线性方程组求解比矩阵乘法更快。

方法难度 5 / 5约 120 分钟经得起时间
读之前最好知道
1矩阵乘法指数 ω 与算法复杂度
2Krylov 子空间方法
3条件数与数值稳定性
4随机化算法

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用e79 · 2021-03

“a link to the paper discussed in the article for anyone who is curious:”

给出文章所讨论论文的链接,供感兴趣的人阅读
New algorithm breaks speed limit for solving linear equations原评论 ↗
被提交为 story · 2 次