Timeline for Why is fast matrix multiplication impractical?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2023 at 17:45 | comment | added | Vectornaut | @RBarryYoung: When I think of numerical linear algebra, computing with graph adjacency matrices, solving discretized differential equations, and calculating weighted autocorrelations are applications that come to mind—so 500 by 500 is indeed small. I don't think the need for stuff like this is limited to scientific computing. Surely there are marketing businesses that want to find autocorrelations of daily time series more than two years long, and logistics companies that want to multiply adjacency matrices of graphs with more than 500 vertices! | |
| Oct 9, 2022 at 9:33 | comment | added | Aurel | Henri, from what I have read, the DeepMind $4\times 4$ multiplication is only valid in characteristic $2$. Apparently, this is supposed to be a practical general matrix multiplication asymptotically faster than Strassen's. | |
| Oct 9, 2022 at 8:23 | history | edited | Henri Cohen | CC BY-SA 4.0 |
new result
|
| May 1, 2022 at 16:56 | comment | added | RBarryYoung | @JiaweiRen The Jianyu-Huang article cited above mentions "as low as 500" as the turnaround point. That may be considered small in some domains (such as scientific computing) but for general purpose programming a 500x500 array is far from what most would call a "small" matrix. | |
| Apr 29, 2022 at 8:17 | comment | added | BrockenDuck | @JiawenRen There is no exact value. For the numerical bounds on the current best matrix multiplication algorithm, you can look at section 6.5 of this paper | |
| Apr 29, 2022 at 5:13 | comment | added | Jiawei Ren | How huge is it? I cannot find an exact value about it. | |
| Apr 29, 2022 at 4:04 | comment | added | Brendan McKay | Indeed. According to researchgate.net/profile/Jianyu-Huang/publication/… Strassen's method can be good even for quite small matrices. | |
| Apr 28, 2022 at 19:07 | history | answered | Henri Cohen | CC BY-SA 4.0 |