= Matrix-chain multiplication
Given a fixed <sequence> of compatible <matrices> $A_1,\ldots,A_m$, choose a binary parenthesization of $A_1\cdots A_m$ that minimizes the number of scalar multiplications in ordinary <matrix multiplication>. The order of the <matrices> is fixed: parenthesization changes the grouping, not the operand order. <Associativity> preserves the product while intermediate <matrix> dimensions change the cost. The possible binary groupings are counted by the <Catalan number> $C_{m-1}$ for $m\geq1$.
Back to article page
