ECCC-Report TR20-030https://eccc.weizmann.ac.il/report/2020/030Comments and Revisions published for TR20-030en-usMon, 09 Mar 2020 17:23:38 +0200
Paper TR20-030
| Barriers for Rectangular Matrix Multiplication |
Matthias Christandl,
François Le Gall,
Vladimir Lysikov,
Jeroen Zuiddam
https://eccc.weizmann.ac.il/report/2020/030We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously known barriers, both in the numerical sense, as well as in its generality. We prove our result using the asymptotic spectrum of tensors. More precisely, we crucially make use of two families of real tensor parameters with special algebraic properties: the quantum functionals and the support functionals. In particular, we prove that any lower bound on the dual exponent of matrix multiplication $\alpha$ via the big Coppersmith-Winograd tensors cannot exceed 0.625.Mon, 09 Mar 2020 17:23:38 +0200https://eccc.weizmann.ac.il/report/2020/030