5
$\begingroup$

I know that the fastest known algorithm for multiplying two $m \times m$ matrices runs in time $m^{\omega}$, where currently we have $\omega = 2.3728596$ due to Virginia Williams's latest result (see here and here). But I'm not sure how this translates to matrices with other dimensions.

In terms of $\omega$, $l$, $m$, and $n$, what is the fastest known algorithm for multiplying an $l \times m$ and $m \times n$ matrix?


Notes:

  • If $l > m$ and $n > m$ I think it would just be $O(lnm^{\omega - 2})$. But I'm not sure about when $l < m$ or other such cases.

  • Yuval Filmus's answer points to Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor, Le Gall and Urrutia 2017. But it is difficult for me to extract a precise idea of how these results translate to $l \times m$ by $m \times n$. I think there is some implicit knowledge involved in the easy cases and hard cases of multiplying an $n \times n^\alpha$ and $n^\alpha \times n$ matrix.

  • Coppersmith 1982, Rapid Multiplication of Rectangular Matrices, appears to be the seminal reference, where the quantity I am interested in is called Rank<K,M,N>, but does not provide a derivation of it.

  • The important basic fact that these references show is that multiplying an $n \times n^\alpha$ and $n^\alpha \times n$ matrix takes approximately $\tilde{O}(n^2)$ time (less than $n^{2 + \epsilon}$ for any $\epsilon$) for sufficiently small $\alpha$, approximately $0.313$ or less, currently. I expect that going from this to $l \times m$ and $m \times n$ is more or less direct or well-known, but this is not my area and the complexity for $l \times m$ and $m \times n$ is not stated directly.

$\endgroup$
2

2 Answers 2

3
$\begingroup$

More "down to earth" fast matrix multiplication algorithms are described at this url. If you know better ones for these matrix sizes (all up to 32x23), their definitions is welcome.

$\endgroup$
1
  • $\begingroup$ This is excellent and interesting, thank you! $\endgroup$ Jan 6, 2022 at 17:07
2
$\begingroup$

Le Gall improved over Williams' result, and Alman and Williams improved over his result. The latter is currently the state of the art for multiplying two square matrices.

The best known algorithms for multiplying an $n \times n^\alpha$ by an $n^\alpha \times n$ matrix ("rectangular matrix multiplication") can be found in Le Gall and Urrutia.

If your dimensions are any different, try to reduce your problem to one of the above. For example, let $t = \min(l,m,n)$. You can think of your problem as that of multiplying an $l/t \times m/t$ matrix with an $m/t \times n/t$ matrix, both of them having $t \times t$ entries. The corresponding complexity is $lmn t^{\omega-3+o(1)}$ (recall that $\omega$ is an infimum!), which is roughly $lmn/t$ if $\omega = 2$. If you only want to assume currently known bounds on $\omega$, you could get better bounds in some cases using rectangular matrix multiplication.

$\endgroup$
7
  • $\begingroup$ The "latest" result and paper I mentioned is Alman and Williams. Thanks for the very useful Le Gall Urrutia paper. I am not sure I can directly see how that applies to $l \times m$ by $m \times n$, though. They seem to be assuming some restrictions on $\alpha$ in the abstract. $\endgroup$ Dec 12, 2021 at 23:32
  • $\begingroup$ Spend some effort and also read the introduction to their paper. $\endgroup$ Dec 12, 2021 at 23:34
  • $\begingroup$ Dear Yuval, I hardly think "spend some effort" is a necessary addition. We both understand everyone is quite busy. For instance, you didn't spend the effort to click on the link to the paper in my question, or take a note of the value of $\omega$, to see that I was already mentioning the result you stated in your first sentence. $\endgroup$ Dec 12, 2021 at 23:37
  • $\begingroup$ You mentioned only reading the abstract. You might gain some insight by also reading the introduction, which addresses the question of which $\alpha$ are handled by the paper and to what extent. $\endgroup$ Dec 12, 2021 at 23:39
  • 1
    $\begingroup$ There’s no simple answer. Assuming $l \leq n,m$, you can think of your problem as multiplying a $1 \times m/l$ matrix by an $m/l \times n/\ell$ matrix, with entries being themselves $\ell \times \ell$ matrices. This has complexity $O(\ell m n \ell^{\omega - 3 + o(1)})$. When $m$ is the smallest you could potentially get even better using rectangular matrix multiplication (second paragraph). $\endgroup$ Dec 13, 2021 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.