0
$\begingroup$

There are algorithms that speed up matrix multiplication over the naive $n^3$ algorithm. But supposing you have 3 matrices $A$, $B$ and $C$, is there a way to compute $ABC$ that is asymptotically faster than first computing $AB$ and then computing $(AB)C$? Let's assume the matrices are square and dense.

This question was inspired by this post on math stack exchange.

$\endgroup$

1 Answer 1

1
$\begingroup$

No. If you can multiply two $n \times n$ matrices in time $O(f(n))$ then you can also multiply three matrices $A,B,C$ in the same asymptotic running time by first computing $M=AB$ and then $MC$.

Conversely, if you can multiply three matrices in time $O(f(n))$ then you can also multiply two matrices in the same asymptotic running time by letting one of the matrices be the identity matrix.

$\endgroup$
1
  • $\begingroup$ What might be possible is to calculate (A*B)*C not in twice the time, but maybe 1.5 times the time of a single product. No idea how. $\endgroup$
    – gnasher729
    Nov 28, 2023 at 22:43

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.