Course: 113-1 Introduction to Algorithms. Lecturer: Huilan Chang. 2024.11.28 Reference: Chained Matrix Multiplication (Section 3.4 in Foundations Of Algorithms by Neapolitan)

Preliminaries

• Multiply matrices in the standard way. e.g. If $A$ and $B$ are $2\times 3$ and $3\times 4$ matrices, respectively, then $A\times B$ takes $2\cdot 3\cdot 4=24$ elementary multiplications.
• Consider the multiplication $A_1\times A_2\times A_3$ (10×100, 100×5, 5×50, respectively) Only two ways to compute:
  • $((A_1A_2) A_3)$: 10×100×5 + 10×5×50 = 7500 multiplications are used. (optimal!)
  • $(A_1(A_2A_3))$: 100×5×50 + 10×100×50 = 75000 multiplications are used.
• Goal: Develop an algorithm that determines the optimal order for multiplying $n$ matrices. $A_1 A_2A_3 \cdots A_n$

Brute-force method (暴力法)

• Considering all possible orders is at least exponential-time： Let $t_n$ to be the number of different orders of multiplying $A_1 A_2A_3 \cdots A_n$. Then $t_n\geq 2^{n-2}$. (單種類就有這麼多種） Proof. Consider two different kinds of orders:

Thus $t_n\geq 2t_{n-1}$. Therefore, $t_n\geq 2^{n-2}t_2=2^{n-2}$. QED.

• The Catalan number $C_n=\frac{1}{n+1}{2n\choose n}$ $C_0 = 1$, $C_1 =1 = t_2$ : $(A_1A_2)$ $C_2= 2 =t_3$: $((A_1 A_2) A_3)$, $(A_1 (A_2A_3))$ $C_3 = 5 = t_4$: 用最後一個(矩陣)相乘來分類：$t_4=t_1t_3+t_2t_2+t_3t_1=2+1+2=5$ List all the orders:

  Fact: $t_n=C_{n-1}$ and $C_n\sim \dfrac{4^n}{n^{1/2}\sqrt{\pi}}$ (exponential).

Dynamic Programming (動態規劃)

<aside>

Definition. For $1\leq i\leq j\leq n$, let

$M[i][j]$ = the minimum number of multiplications to multiply $A_i$ through $A_j$ if $i<j$. $M[i][i]= 0$.

</aside>

• Consider the multiplication $A_1A_2A_3A_4A_5A_6$, where $A_i$ is a $d_{i-1}\times d_i$ matrix. The optimal order for the multiplication must have one of these factorizations:

For $k=1\cdots 5$, the minimum number of multiplications for the $k$-th factorization is $M[1][k]+M[k+1][6]+d_0d_kd_6$ Then $M[1][6]=\displaystyle\min_{1\leq k\leq 5} M[1][k]+M[k+1][6]+d_0d_kd_6$.

<aside>

Generally, $M[i][j]=\displaystyle\min_{i\leq k\leq j-1} M[i][k]+M[k+1][j]+d_{i-1}d_kd_j$ if $i<j$, and

$M[i][i]=0$.

</aside>

注意：當中用到一個重要的性質”optimal substructure”: The optimal order for multiplying $n$ matrices contains the optimal order of the multiplication of some matrices within it. Example. If $(A_1(((A_2(A_3 A_4)) A_5) A_6))$ is optimal, then $((A_2(A_3 A_4)) A_5)$ is optimal for multiplying $A_2$ through $A_5$.

• An efficient algorithm using dynamic programming to compute $M[i][j]$ in steps: (Bottom-up) Example. $n=6$ and $d=(5, 2, 3, 4, 6, 7, 8)$. Then $M=$