算法与理论计算机2025arxiv.org
X X^t 可以更快
X X^t can be faster
专业 · 约 90 分钟读完前置知识：线性代数、矩阵乘法算法、浮点运算
导读
这篇论文研究计算 X·Xᵀ（结果为对称矩阵的矩阵乘法）能否比通用矩阵乘法更快，提出了利用对称结构的加速算法。评论者主要讨论这类理论加速在真实硬件上是否实际有效。
HN 关注点：理论算法改进（减少乘法次数）与实际硬件性能之间的差距，以及它对大规模 AI 计算成本的潜在影响。
HN 评论精选
这几条评论里：质疑 2 补充 2
质疑质疑理论加速在真实硬件上的实际效果，并分享利用对称性加速的实践经验
这会不会像 Karatsuba 算法那样，理论上更快但在真实硬件上并不快？另外值得注意：如果已知结果是对称的（如 X·Xᵀ），可以更快。比如 cuBLAS 里针对对称结果优化的 syrk 在我经验中并不比 gemm 快，所以更好的做法是分块小乘法只填一个三角，再把该三角复制到另一个。
meisel查看英文原文
Is this like the Karatsuba algorithm, where it's theoretically faster but not actually faster when run on real hardware? Btw, it's worth noting that if you know that the result will be symmetric (such as is the case for X * X^T), you can make things faster. For example in cuBLAS, cublas*syrk (the variant optimized for when the result is symmetric) IME isn't faster than gemm, so what you can do instead is just do smaller multiplications that fill in one of the two triangles piece by piece, and then copy that triangle to the other one.
补充担心减少乘法、增加加法的优化会牺牲数值精度
有没有研究者关注在加速这些算法的同时保持结果的最大精度？这类优化通常是用更少的乘法换更多的加法，但据我所知浮点加减法有精度风险，而乘法是无害的。另外使用 FMA（融合乘加）指令也会有益。
ttoinou查看英文原文
Are there researchers interested in accelerating these algorithms while also keeping the maximum accuracy of the results ? This and others optimizations are trading less multiplication for more additions, but from the little I know, on floating point additions and subtractions are risky precision wise, while multiplications are harmless. Also using FMA fused multiply add operations would be beneficial.
质疑好奇该优化对大规模 AI 算力成本的实际价值
那么如果一家 AI 公司花 50 亿美元建集群，这个优化能值 2.5 亿美元吗？
BryanLegend查看英文原文
So if an AI company spends $5B on a cluster, is this optimization worth $250m?
补充思考该计算的实际应用场景
我一时想不出什么具体应用，除了方阵中用迭代矩阵乘法近似求特征向量。但我不知道实际求特征向量（或其他分解）用的是什么方法。
Scene_Cast2查看英文原文
I can't name any applications off the top of my head, other than iterative matrix multiplication for approximate eigenvector finding in square matrixes. But I don't know what's actually used for finding eigenvectors (or other decompositions for that matter).
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2025Hacker News 讨论帖201 分 · 60 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选