HackerPapers

arXiv:2210.10173cs.DS

Faster Matrix Multiplication via Asymmetric Hashing

Ran Duan, Hongxun Wu, Renfei Zhou

Abstract

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.

arXiv comments
87 pages, in FOCS 2023
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Jun 2023 to Mar 2024.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Show HN: Matrix Multiplication with Half the Multiplications 1 comment

    • 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…

      barfbagginusView on HNParent context

  2. Is parallel programming hard, and, if so, what can you do about it? 1 comment

    • >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…

      anchovy_View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.