0
Explain Strassens matrix multiplication

Subject: Analysis Of Algorithm

Topic: Divide Aqnd Conquer

Difficulty: High

aoa(14) • 3.5k  views
0

Strassen’s matrix multiplication

1. Let A and B be two nn matrices, that is, each having n rows and n columns. If C=AB, then the product matricx C will also have n rows and n columns.
2. An element C[i, j] can now be found using the formula

$$C [i, j] = \sum_{k=0}^{n-1}A[i,k]*B[k,j]$$

3. The method of multiplying two matrices is known as the classic matrix multiplication method. Using the above formula, we may write the following statements:

for( i=0; i < n; i++)

for( j=0; j<n; j++)

{

C[i] [j] =0;

for( k=0;k<n;k++)

C[i][j]=c[i][j]+a[i][k]*b[k][j];

}

4. It can be easily verified that the complexity of the method is $O (n^3)$.

5. Strassen’s matrix multiplication can be used only when n is a power of 2i.e. $n=2^k$. If n is not a power of 2 then enough rows and columns of zeros can be added to both A and B so that the resulting dimension are a power of 2.
6. In this method matrix A and B are splitted into 4 squares sub-matrices where each sub-matrices has dimension of n/2. Now the product is found as shown:

$1\begin{matrix} A_{11}&A_{12} \\ A_{21}&A_{22} 1 \\ \end{matrix}1$ $\hspace{0.5cm}$ $1\begin{matrix} B_{11}&B_{12} \\ B_{21}&B_{22} 1 \\ \end{matrix}1$ $\hspace{0.5cm}$ $\begin{matrix} C_{11}&C_{12} \\ C_{21}&C_{22} 1 \\ \end{matrix}1$

$P = (A_{11}+A_{22}) ( B_{11}+B_{22}) \\ Q = (A_{21}+A_{22}) B_{11} \\ R = A_{11}( B_{12}-B_{22})$

$S= A_{22}( B_{21}-B_{11})$

$T= (A_{11}+A_{12})B_{22} \\ U= (A_{21}-A_{11}) ( B_{11}+B_{22}) \\ V= (A_{12}-A_{22}) ( B_{21}+B_{22}) \\ C_{11} = P+S-T+V \\ C_{12} = R+T \\ C_{21} = Q+S \\ C_{22} P+R-Q+U$

It is observed that all c [i, j] can be calculated using a total of 7 multiplications and 18 additions or subtractions.

7. Consider the following example:

$\begin{matrix} 1&2 \\ 4&5 \\ \end{matrix}$ $\hspace{0.5cm}$ * $\begin{matrix} 6&8 \\ 7&9 \\ \end{matrix}$ $\hspace{0.5cm}$ $\begin{matrix} C_{11}&C_{12} \\ C_{21}&C_{22} 1 \\ \end{matrix}1$

Now we want to find C12, this can be done as shown:-

R=1*(8-9) =-1,

T= (1+2) *9=27,

C_12 = -1+27=26

Similarly, C_21 can be found as shown

Q= (4+5) *6=54

S= 5*(7-6) =5

C_21 = 54+5 =59

8. It is not necessary that n should be always 2. If n>2 then the same formula can be used but now it will be done recursively. The same formula will be continuously applied on smaller sized matrices till n gets reduced to 2. When n=2, this will be terminating condition of recursion and now multiplication is done directly.