Assume we work on the complex field $\mathbb{C}$. And we use $\langle p,q,r\rangle$ to denote the bilinear complexity of product of a $p\times q$ matrix and a $q\times r$. Recently I read a paper on the bilinear complexity of $5\times 5$ matrix product. And it reminds me to consider the bilinear comlexity of matrix product with lower dimension. However, the only nontrivial result I find is in the paper 'On the complexity of the multiplication of matrices of small formats'. The author gave a bound that $33\le\langle 4,4,4\rangle\le49$. This paper was published 20 years ago. I wonder if there are some advances on the estimation of the complexity after this work.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In the paper you mention, Bläser improves the lower bound to 34.
To my knowledge, there was no progress on this specific problem. The recent Nature paper which used machine learning to solve the usual optimization problem improved the upper bound to 47 in characteristic 2, but not over $\mathbb{C}$. There were also some new lower bounds (Landsberg, Massarenti & Raviolo), but they only give improvement for larger sizes.
answered Dec 20, 2023 at 8:33