Matrix Chain Multiplication
Choose parentheses for four compatible matrices and compare the resulting arithmetic costs.
Free theory articleChoose parentheses for four compatible matrices and compare the resulting arithmetic costs.
Concept & interpretation
Matrix chain multiplication is a classic interval dynamic programming problem that finds the optimal parenthesization of compatible matrices A1, A2, A3, and A4 to minimize total scalar multiplications without reordering the matrices.
Experiment
Test how bottleneck interior dimensions vs outer dimensions drive optimal parenthesization in https://riano.app/module/matrix-chain-multiplication:
- Start with default dimensions (5, 2, 4, 3, 6) and click Step six times to fill the three length-2 intervals, two length-3 intervals, and final length-4 interval in order.
- Set alternating dimensions d0 = 2, d1 = 7, d2 = 3, d3 = 8, d4 = 4 and click Finish to observe cost 154 and (((A1*A2)*A3)*A4).
- Set all dimensions to 1 or all dimensions to 9 to verify tie breaking when every split candidate yields the exact same scalar multiplication count.