next up previous
Next: About this document ... Up: CSC364 Tutorial Week 2 Previous: Proof

Matrix Chain Multiplication

Given matrices $A_1, A_2, ... A_n$ with $A_i$ having dimensions $p_i \times q_i$ such that $p_i = q_{i-1}$ (so that we can multiply them) find the product, $A_1A_2 ... A_n$.

\( M \left[i, j\right] = \) optimal cost of finding $A_iA_{i+1}...A_j$

\( \tilde{M} \left[i, j\right] = \left\{ \begin{array}{l@{\quad,\quad}l} 0 &... ...t] + M\left[k+1, j\right] + p_{i-1}p_kp_j \right\} & i < j \end{array}\right.\)

Figure 2: Matrix Chain Example
\begin{figure}\centering \scalebox{0.5}{\epsfig{file=MCex.eps}} \end{figure}


Raymond Fingas 2002-01-18