Class Code: AMC621 Instructor: Huilan Chang

🔹Multiply two $n\times n$ matrices in the standard way:

• The number of multiplications ($\cdot$) is _________.
• The number of additions (+) is ___________.

◼️ Strassen’s method

🔹In 1969, Strassen published an algorithm whose time complexity is $\Theta(n^{2.81})$.

Strassen’s method (先討論 $n$ is a power of $2$)

Compute $M_1:= (A_{11} + A_{22}) (B_{11} + B_{22})$ that is a multiplication of two $\frac{n}{2}\times\frac{n}{2}$ matrices. Similarly compute $M_2$ through $M_7$. Then compute $C_{11}=M_1+M_4-M_5 + M_7$ and similarly compute $C_{12}$, $C_{21}$ and $C_{22}$. Note. We recursively compute $M_1$ through $M_7$ until the matrices are sufficiently small. When the order of matrices is less than or equal to threshold, multiply them in the standard way.

Note. Costs of Multiplying two $2\times 2$ matrices:

| | number of multiplications | number of additions/subtractions | | --- | --- | --- | | Strassen’s method | | | | standard way | | |

🔹 Pseudocode

Strassen( $n$, $A$, $B$)

if ($n≤$ threshold)

compute $C=A\times B$ using the standard algorithm;

else {

partition $A$ into four submatrices $A_{11}, A_{12}, A_{21}, A_{22}$;

partition $B$ into four submatrices $B_{11}, B_{12}, B_{21}, B_{22}$;

compute $C=A\times B$ using Strassen’s method;

// ex. recursive call: Strassen($n/2$, $A_{11}+A_{22}$, $B_{11}+B_{22}$) to obtain $M_1$.

}

Example.

$\begin{bmatrix}1 & 2 & 3 & 4\\5 & 6&7&8\\9&1&2&3\\4&5&6&7\end{bmatrix}\times \begin{bmatrix} 8&9&1&2\\3&4&5&6\\7&8&9&1\\2&3&4&5\\\end{bmatrix}$ with “threshold=1” and “threshold=2”.