Matrix-chain Multiplication

Matrices multiplication ABCD has multiple possible operations: A(BCD), A(BC)D, .., etc.

Wiki: Matrix Chain Multiplication問題

• 如何用最少的相乘operations求出矩陣相乘？最直觀的方法就是把()擺到所有可能的地方。
• 如果利用 recursive 的方法，會有一些 sub-problems 會一直重複計算。
• 建立 temporary array m[][] 來避免以上狀況，以空間換取時間。

How to get the specific solution?

• Use split markers to record.

• Each entry s[i,j] records a value of k such that an optimal parenthesization of $A_i ...A_j$ splits the product between $A_k$ and $A_{k+1}$, 使得 $(A_iA_{i+1}...A_k)$ 和 $(A_{k+1}...A_j)$ 都各自擁有最小軄值。

  

• For example,
  • $A_3A_4$ split value k = 3
  • $A_3A_4A_5$ with k = 3 $\rightarrow$ $A_3(A_4A_5)$
  • $A_3A_4A_5$ with k = 4 $\rightarrow$ $(A_3A_4)A_5$

Implementation

$Matrix Size: A_1\rightarrow p_0p_1, A_2\rightarrow p_1p_2, ..,etc.$

Matrix-Chain(array p[0 .. n], int n) {

    FOR i = 1 TO n DO m[i, i] = 0;     // initialize

    FOR L = 2 TO n DO {                // L = length of subchain
        FOR i = 1 TO n − L + 1 do {
            j = i + L − 1;
            m[i, j] = infinity;

            FOR k = i TO j − 1 DO {    // check all splits
                q = m[i, k] + m[k + 1, j] + p[i − 1] p[k] p[j];
                IF (q < m[i, j]) {
                    m[i, j] = q; 
                    s[i, j] = k; 
                }
           } 
        } 
     }
     return m[1, n](final cost) and s;
}

Example

Answer: $(A_1A_2)((A_3A_4)A_5)$

References

• chainMatrixMult
• 陳士杰 DP