###### tags: `ADA 4.1` `Matrix Multiplication`
# ADA 4.1: Matrix Multiplication

Textbook Chapter 4.2 - Strassen’s algorithm for matrix multiplication

:::info
💭**複習矩陣乘積計算方式：**
兩個矩陣元素分別以箭頭方向兩兩配對，
將乘積加總後取得箭頭交叉位置的值
:::
# Matrix Multiplication Problem

$\text{Input: two }n \times n \text{ matrix } A \text{ and } B$
$\text{Output: the product matrix } C = A \times B$


## SQUARE-MATRIX-MULTIPLY

$C(i, j)=\sum_{k=1}^n+A(i,k) \cdot B(k,j)$
* Each entry takes n multiplications
* There are total $n^2$ entries
⇨ $\Theta(n)\Theta(n^2)=\Theta(n^3)$

**Upper bound: $O(n^3)$**：Native 方法所得
**Lower bound: $\Omega(n^2)$**：單一 Matrix 元素遍歷最低次數

#### 如何降低 Upper bound?

# Divide-and-Conquer

* We can assume that $n = 2^k$ for simplicity
* Otherwise, we can increase n s.t. $n=2^{[\log_2n]}$
* $n$ may be twice large as the original in this modification


講方形矩陣的邊長 $n$ 假定為 2 的 $k$ 次方，即可將矩陣拆成 4 個小矩陣
單一個小矩陣的計算方式相同，以此類推：

$C_{11}=A_{11}B_{11}+A_{12}B_{21}$
$C_{12}=A_{11}B_{12}+A_{12}B_{22}$
$C_{21}=A_{12}B_{11}+A_{22}B_{21}$
$C_{22}=A_{21}B_{12}+A_{22}B_{22}$

## Divide-and-Conquer algorithm time complexity

* Base case: $\Theta(1)$
* Divde submatrices: $\Theta(1)$
* MatrixMultiply(n/2, A$_{xy}$, B$_{xy}$): $8\times T(n/2)$
* Submatrices + submatrices: $4\times\Theta((n/2)^2) = \Theta(n^2)$

Time for running Divide-and-Conquer algorithm:

$T(n)=\begin{cases}
\Theta(1) &\text{if }n=1\\
8T(n/2)+\Theta(n^2)&\text{if }n\ge2
\end{cases}$

:::info
**💭回顧一下 Master Method**

$T(n)=\begin{cases}
O(1) &\text{if } n\le 1\\
a\cdot T(\frac nb)+f(n) &\text{if } n > 1,
\end{cases}$

where $a \ge 1$ and $b > 1$ are constants.

- Case 1: If $f(n)=O(n^{\log_b{a-\epsilon}})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_ba})$.
- Case 2: If $f(n)=\Theta(n^{\log_ba})$, then $T(n)=\Theta(n^{\log_ba}\cdot \log n)$.
- Case 3: If
- $f(n)=\Omega(n^{\log_b{a+\epsilon}})$ for some constant $\epsilon > 0$, and
- $a\cdot f(\frac nb)\le c\cdot f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.
:::

在 Master Mathod 中代入參數
$n^{log_ba}=n^{log_28}=n^3$
可得知 $\epsilon <$ 0 故套用 case 1 可得到 $T(n)=\Theta(n^3)$

#### Divide-and-Conquer 與 Square-Matrix-Multiply 有相同的複雜度

# Strassen's method

[施特拉森演算法 Wiki](https://zh.wikipedia.org/zh-tw/施特拉森演算法)

#### 1969 年時通過減少乘法次數降低矩陣乘法複雜度

已知：
$C_{11}=A_{11}B_{11}+A_{12}B_{21}$
$C_{21}=A_{21}B_{11}+A_{22}B_{21}$
...
可得：
$C_{11}=A_{11}(B_{12}-B_{22})+(A_{11}+A_{12})B_{22}=M_3+M_5$
$C_{21}=(A_{21}+A_{22})B_{11}+A_{22}(B_{21}-B_{11})=M_2+M_4$
...
:::info
💭複習數學
$ac+ad+bc+bd=(a+b)(c+d)$
4 multiplications -> 1 multiplications
3 additions -> 2 additions
:::
將 $C_{11}\ C_{12}\ C_{21}\ C_{22}$ 進行簡化，暫存且重複使用 $M_1\ M_2\ M_3\ M_4\ M_5\ M_6\ M_7$：

$C_{11}=M_1+M_4-M_5+M_7$
$C_{12}=M_3+M_5$
$C_{21}=M_2+M_4$
$C_{22}=M_1-M_2+M_3+M_6$
$M_1=(A_{11}+A_{22})(B_{11}+B_{22})$
$M_2=(A_{21}+A_{22})B_{11}$
$M_3=A_{11}(B_{12}-B_{22})$
$M_4=A_{22}(B_{21}-B_{11})$
$M_5=(A_{11}+A_{12})B_{22}$
$M_6=(A_{21}-A_{11})(B_{11}+B_{12})$
$M_7=(A_{12}-A_{22})(B_{21}+B_{22})$

## Strassen's method algorithm time complexity

* Base case: $\Theta(1)$
* Divde submatrices: $\Theta(1)$
* Conquer: $7\times T(n/2)+\Theta((n/2)^2)$
* Combine: $\Theta(n^2)$

Time for running Strassin(n, A, B):
$T(n)=\begin{cases}
\Theta(1) &\text{if }n=1\\
7T(n/2)+\Theta(n^2)&\text{if }n\ge2
\end{cases}$

Apply master method:
$T(n)=\Theta(n^{log_27})$~$\Theta(n^{2.807})$

* Disadventures:
* Lager constant factor than it in native approch: $C_1n^{log_27},\ C_2n^3 \text{ where }C_1>C_2$
* Less numerical stable than the native approch
* Larger errors accumlate in non-integer computation due to limited precison
* The submatrices at the levels of recursion consume space
* Faster algorithms exist for sparse matrices
* Adventures:
* Find the crossover point and combine two subproblems