按年被提到
20222023 · 1 次2026
算法与数据结构›经典算法与数据结构·arXiv:2210.10173 · cs.DS

Faster Matrix Multiplication via Asymmetric Hashing

Ran Duan, Hongxun Wu, Renfei Zhou · 2022
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2023-06-14 · 最近 2024-03-16
2不同的人
2活跃月份
2讨论串
72被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by $ω$. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a "combination loss", and we partially compensate for it using an asymmetric version of CW's hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of $ω<2.371866$, which improves the previous best bound of $ω<2.372860$ [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of $2.3725$ in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论anchovy_ · 2023-06

“>However, an O(n^3) algorithm will always loose out to an O(n^2*log(n)) algorithm, when the input gets big enough. Sure, this might be the case from a theoretical point of view (as per definition) but this completely disregards the hidden constants that come to light when actually implementing an algorithm. There's a reason why for instance a state-of-th…”

Is Parallel Programming Hard, and, If So, What Can You Do About It? v2023.06.11a原评论 ↗
评论barfbagginus · 2024-03

“I made two really bad misunderstandings which I completely own. I can't seem to edit it, so please let this be my refutation and explanation of my own mistake. First misunderstanding: I assumed this was a new large matrix multiplication algorithm building on the hype from last week or so where we saw this paper: https://arxiv.org/abs/2210.10173 It is no…”

Show HN: Matrix Multiplication with Half the Multiplications原评论 ↗