Matrix-Chain Multiplication Problem

假設有n個矩陣相乘，矩陣相乘是有順序性的，不能夠使用交換律(commutative property)，但是使用結合律(associative property)並不影響相乘的結果。
結合律的方式有\( (n-1)! \)種表示矩陣相乘的方式，不同的結合方式，中間的計算矩陣內乘法的次數會有所不同，乘法數量差異極大，所以需要找出最小的乘法量的順序，才能事半功倍。

如果使用暴力破解，找出最小乘法量的結合律表示，需要 \( \Omega(\frac{4^n}{n^{\frac{3}{2}}})=\Omega(2^n) \)的Time Complexity，是指數的倍增方式，如果有100個矩陣要相乘，那最糟糕要找\( 2^{100} \)次，才能找到最小乘法量的結果，那不必找最小乘法量，直接對這100個矩陣相乘，時間可能都比較快。

Matrix-chain具有最佳結構。
最佳結構描述:
Def:
\( A_{i\dots j} = A_iA_{i+1}\dots A_j \)
其中有個\( k, i\leq k < j \)，可將 \( A_{i\dots j} \)拆成 \( A_{i\dots k}\times A_{k+1\dots j} \)
這樣就可以討論\( k \)在多少的時候，會有最小乘法量
這樣原本
\( A_iA_{i+1}\dots A_{j} \)
\( = A_{i\dots k}\times A_{k+1\dots j} \)
也就為結合律表示
\( (A_iA_{i+1}\dots A_{k}) \times (A_{k+1}\dots A_{j}) \)

因有最佳結構，使用Dynamic programming來查出最小乘法量，效率較高。

公式

Def:
\( A_i\in F^{p_{i-1}\times p_i} \)
\( \Rightarrow A_i:p_{i-1}\times p_i \)
Let \( m[i,j] \) is the least number of multiplication.
\[ m[i,j]= \begin{cases} 0 &\text{, if }i=j\\ Min_{i\leq k< j}\{m[i,k]+m[k+1,j]+p_{i-1}\cdot p_k\cdot p_j\} &\text{, if } i< j\\ \infty &\text{, if }i>j\\ \end{cases} \]
解釋:

\( A_i:p_{i-1}\times p_i \)為第i個矩陣，有\( p_{i-1} \)個rows，有\( p_{i} \)個columns
舉例\( A_3\in F^{4\times 3} \)，即\( p_2=4,\;p_3=3 \)。

\( Min_{i\leq k< j}\{m[i,k]+m[k+1,j]+p_{i-1}\cdot p_k\cdot p_j\} \) 為一集合裡找最小的值，集合的產生是由\( i\text{到}(j-1) \)的所有可能產生，每種可能由\( k \)來代表。

\( Min \)裡有三個項目
\( m[i,k] \)為\( A_i \)到\( A_k \)的最小乘法量。
\( m[k+1,j] \)為\( A_{k+1} \)到\( A_j \)的最小乘法量。
\( p_{i-1}\cdot p_k\cdot p_j \)為\( A_{i\dots k} \)和\( A_{(k+1)\dots j} \)的乘法量。

無限大視為不可能，因為矩陣不能夠有交換律。

舉例及填表

What is the least number of multiplications to compute matrix \( ABCDE \)?
MatrixDimensions
A\( 2\times 4 \)
B\( 4\times 3 \)
C\( 3\times 2 \)
D\( 2\times 5 \)
E\( 5\times 1 \)
矩陣順序是\( ABCDE \)，為了方便計算，第一個matrix用\( A_1 \)代替 ，第二個matrix用\( A_2 \)代替，以此類推，為\( A_1A_2A_3A_4A_5 \)。
\( p_0=2 \)
\( p_1=4 \)
\( p_2=3 \)
\( p_3=2 \)
\( p_4=5 \)
\( p_5=1 \)

開始填表

有兩個表格
  1. 最小乘法量
  2. 需要掛號 ')' 到哪個matrix的後面

可以多加一個變數去紀錄怎樣的結合律是最小的乘法量，這裡用變數k表示。
記在表格內上方，下方為最小乘法量的數目。
手算
m i\j \( A_1 \) \( A_2 \) \( A_3 \) \( A_4 \) \( A_5 \)
\( A_1 \) \( 0 \) \( k=1 \)
\( 24 \) 		\( k=2 \)
\( 36 \) 		\( k=3 \)
\( 56 \) 		\( k=1 \)
\( 36 \)
\( A_2 \) - 0 \( k=2 \)
\( 24 \) 		\( k=3 \)
\( 64 \) 		\( k=2 \)
\( 28 \)
\( A_3 \) - - 0 \( k=3 \)
\( 30 \) 		\( k=3 \)
\( 16 \)
\( A_4 \) - - - 0 \( k=4 \)
\( 10 \)
\( A_5 \) - - - - 0

填表順序為 由左上到右下、由左至右。
最後最右上角的值，即為\( ABCDE \)的最小乘法量\( =36 \)
拿其中\( m[2,5]=28 \)來說明(即\( A_2A_3A_4A_5 \))
在得出\( m[2,5] \)的可能set為\( \{ 28,42,84 \} \)，其中最小為28所以\( m[2,5]=28 \)。

計算過程
公式裡的\( k \)為\( i\leq k< j \)那\( m[2,5] \)的\( k \)就在\( 2\leq k< 5 \)中，

討論k=2
\( m[2,2]+m[2+1,5]+p_{2-1}p_2p_5 = 0 + 16 +4\cdot 3\cdot 1=28 \)

討論k=3
\( m[2,3]+m[3+1,5]+p_{2-1}p_3p_5 = 24 + 10 +4\cdot 2\cdot 1=42 \)

討論k=4
\( m[2,4]+m[4+1,5]+p_{2-1}p_4p_5 = 64 + 0 +4\cdot 5\cdot 1=84 \)

最後得出在\( k=2 \)時( 也就是\( (A_2)(A_3A_4A_5) \) )，有最小乘法量為\( 28 \)。

還原掛號的表格:(注意index不一樣, 列index 1~4, 行index 2~5)
k \( 2 \) \( 3 \) \( 4 \) \( 5 \)
\( 1 \) \( 1 \) \( 2 \) \( 3 \) \( 1 \)
\( 2 \) - 2 \( 3 \) \( 2 \)
\( 3 \) - - 3 \( 3 \)
\( 4 \) - - - 4
ex. \( k[i,j]=\alpha \;\)指的是\( A_iA_{i+1}\dots A_\alpha\dots A_j \)在\( A_\alpha \)後括起來, 像是\( (A_i\dots A_\alpha)(A_{\alpha+1}\dots\dots A_j) \)

推導括號的表示

看\( k[1,5] \)的\( k \)值為\( 1 \)， 即\( (A_1)(A_{2\dots 5}) \)。
\( A_1 \)已經不能分成其他矩陣相乘，再討論\( A_{2\dots 5} \)的括號方式。

看\( k[2,5] \)的\( k \)值為\( 2 \)， 即\( (A_1)((A_2)(A_{3\dots 5})) \)。
\( A_2 \)已經不能分成其他矩陣相乘，再討論\( A_{3\dots 5} \)的括號方式。

看\( k[3,5] \)的\( k \)值為\( 3 \)， 即\( (A_1)((A_2)((A_3)(A_{4\dots 5}))) \)。
\( A_3 \)已經不能分成其他矩陣相乘，再討論\( A_{4\dots 5} \)的括號方式。

看\( k[4,5] \)的\( k \)值為\( 4 \)， 即\( (A_1)((A_2)((A_3)((A_{4})(A_{5})))) \)。
\( A_4 \)和\( A_5 \)已經不能分成其他矩陣相乘完成推導。

代回\( A_1=A \)、 \( A_2=B \)、\( A_3=C \)、\( A_4=D \)、\( A_5=E \)，為 \( (A(B(C(DE)))) \)即為最小乘法量的括號表示法。