Strassen algorithm

Traditional matrix multiplication has a complexity of n^3
- ${\begin{bmatrix}C_{11}&C_{12}\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}A_{11}{\color {red}\times }B_{11}+A_{12}{\color {red}\times }B_{21}\quad &A_{11}{\color {red}\times }B_{12}+A_{12}{\color {red}\times }B_{22}\A_{21}{\color {red}\times }B_{11}+A_{22}{\color {red}\times }B_{21}\quad &A_{21}{\color {red}\times }B_{12}+A_{22}{\color {red}\times }B_{22}\end{bmatrix}}.$
Strannen algorithm has a complexity of n^2.8074
In strassen algorithm, matrices are broken down into smaller 2x2 matrices.
Reduces the number of multiplication operation from 8 in the case above to 7.
It defines the following intermediate values:
- ${\begin{aligned}M_{1}&=(A_{11}+A_{22}){\color {red}\times }(B_{11}+B_{22});\M_{2}&=(A_{21}+A_{22}){\color {red}\times }B_{11};\M_{3}&=A_{11}{\color {red}\times }(B_{12}-B_{22});\M_{4}&=A_{22}{\color {red}\times }(B_{21}-B_{11});\M_{5}&=(A_{11}+A_{12}){\color {red}\times }B_{22};\M_{6}&=(A_{21}-A_{11}){\color {red}\times }(B_{11}+B_{12});\M_{7}&=(A_{12}-A_{22}){\color {red}\times }(B_{21}+B_{22}),\\end{aligned}}$
Then uses these values to get the final matrix
- ${\begin{bmatrix}C_{11}&C_{12}\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}\quad &M_{3}+M_{5}\M_{2}+M_{4}\quad &M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.$
only beneficial for large scale matrices. matrix of size 512 sees an improvement of 20%
Winograd form
- This reduces the number of addition and subtraction operations in the strassen algorithm from 18 to 15.
  - ${\begin{bmatrix}a&b\c&d\end{bmatrix}}{\begin{bmatrix}A&C\B&D\end{bmatrix}}={\begin{bmatrix}t+b{\color {red}\times }B&w+v+(a+b-c-d){\color {red}\times }D\w+u+d{\color {red}\times }(B+C-A-D)&w+u+v\end{bmatrix}}$
  - $t=a{\color {red}\times }A,;u=(c-a){\color {red}\times }(C-D),;v=(c+d){\color {red}\times }(C-A),;w=t+(c+d-a){\color {red}\times }(A+D-C)$

[anudeep's space]

Explorer

Explorer

Strassen algorithm

Winograd form

Site Map

Graph View

Backlinks