matrix-chain

Matrix-Chain Multiplication

Definition

Given a chain $⟨A_1,A_2,\dots ,A_n⟩$ of $n$ matrices, $A_i$ has dimension $p_{i-1}\times p_i$, fully parenthesize the product to minimize amount of scalar multiplications. Input is a sequence of dimensions $⟨p_0,p_1,p_2,\dots ,p_n⟩$.

Solution

Brute force takes exponential time.

Let $A_{i:j}$ denote the matrix results from evaluating $A_i{A}_{i+1}\cdots A_j$, $m[i,j]$ be the minimum number of scalar multiplications needed to compute $A_{i:j}$, $s[i,j]$ be the optimal split $k$.

$$m[i,j]=\{\begin{array}{ll}0,& i=j,\\ \min \{m[i,k]+m[k+1,j]+p_{i-1}{p}_k{p}_j:i\le k<j\},& i<j\end{array}$$

Compute shorter chains to longer chains: chain of length $1$ (trivial), $2$, and all the way up to $n$.