Complexity of matrix multiplication with different size

Question

I have three matrices $A, ~B, \text{and} ~C$ which are of size $M \times N, ~ N \times P, ~\text{and}~ P \times M $, respectively. What is the computational complexity of the multiplication $A\times B \times C$?

Answer 1

The "naive" matrix multiplication for $A\times B$ involves multiplying and adding $N$ terms for each of $MP$ entries in $AB$. So the complexity is $O(NMP)$. And then multiplying this $M\times P$ matrix by $C$ requires multiplying and adding $P$ terms for each of $MN$ entries. So the total complexity is $O(M^2N^2P^2)$. (EDIT: This conclusion was incorrect and based on a silly arithmetic mistake that I made. The correct answer, as explained in the comments, is $O(MNP+M^2P)$. Many thanks to @HoldenLee and @Rami Zouari for catching this.)

However, this may not be optimal algorithm. But unfortunately, there's very little information online about the efficiency of non-square matrix multiplication. If all three matrices were square, then the fastest known algorithm for multiplying two of them has complexity $\approx O(N^{2.3729})$; this means that multiplying three $N\times N$ matrices will have complexity just under $O(N^{4.75})$. If the matrices have dimensions that are multiples of each other (or close to multiples) then we can use the square algorithms and block multiplication to speed up the implementation.

I managed to find a paper from 2012 which gets better than $O(N^3)$ results for multiplying $N\times M$ by $M\times N$ matrices, for those values $M<N^{0.30298}$. Assuming that either $N$ or $P$ is less than or equal to $M^{0.30298}$, you could perform one multiplication naively and then use the results of the paper to perform the other multiplication quickly. Depending on the exact values in question, that might be able to get you a result that is better by maybe a factor of $\sqrt{M}$. But in general, I don't think that there are any known algorithms for your specific case that get any better than $O(M^2N^2P^2)$.