= Matrix-chain cost model
For <matrix dimensions> $r\times s$ and $s\times t$, ordinary <matrix multiplication> computes $rt$ <matrix entries>, each using $s$ <scalar multiplications>. Thus its cost is $rst$ <scalar multiplications>, with $rt(s-1)$ <additions> if each sum starts from its first term. Here we minimize only the <scalar multiplication> count, using this dense <matrix multiplication> rule throughout. The counts describe <arithmetic operations>, rather than measured elapsed time; <matrix multiplication> methods that exploit structure or use faster formulas require a different cost rule.
Take <matrices> $A$, $B$, $C$ with <matrix dimensions> $12\times5$, $5\times40$, $40\times3$. Both groupings produce a $12\times3$ <matrix product>, but their intermediate <matrix dimensions> differ:
$$
\begin{aligned}
(AB)C &: \quad 12\cdot5\cdot40+12\cdot40\cdot3=2400+1440=3840,\\
A(BC) &: \quad 5\cdot40\cdot3+12\cdot5\cdot3=600+180=780.
\end{aligned}
$$
The second grouping first compresses $BC$ into a $5\times3$ <matrix>, avoiding the $12\times40$ intermediate <matrix> $AB$. The saving is $3060$ <scalar multiplications>, although both groupings use exactly two <matrix multiplications>. This is why counting only <matrix multiplication> operations hides the interesting choice.
\Image[/matrix-chain-parenthesization-cost-trees.png]
{title=The same matrix product can require 3840 or 780 scalar multiplications}
{description=Original <binary trees> for the three-<matrix> example. Leaves keep $A,B,C$ in the same order. Each internal node gives its resulting <matrix dimensions> and the local <scalar multiplication> cost; adding those costs gives the total.}
<Associativity> permits these regroupings in exact arithmetic; <commutativity> is neither assumed nor generally true for <matrix multiplication>. Swapping $A$ and $B$ here would even make their <matrix product> undefined. In <floating-point arithmetic>, <round-off error> can make the two groupings yield different computed <matrix entries>; the cost optimum alone does not guarantee the smallest numerical error.
Back to article page
