Strassen’s matrix multiplication

                           Strassen in 1969 which gives an overview that how we can find the multiplication of two 2*2 dimension matrix by the brute-force algorithm. But by using divide and conquer technique the overall complexity for multiplication two matrices is reduced.

 This happens by decreasing the total number if multiplication performed at the expenses of a slight increase in the number of addition.

For multiplying the two 2*2 dimension matrices Strassen's used some formulas in which there are seven multiplication and eighteen addition, subtraction, and in brute force algorithm, there is eight multiplication and four addition. 

The utility of Strassen's formula is shown by its asymptotic superiority when order n of matrix reaches infinity.

 Let us consider two matrices A and B, n*n dimension, where n is a power of two.

 It can be observed that we can contain four n/2*n/2 submatrices from A, B and their product C. 

C is the resultant matrix of A and B.

Procedure of Strassen matrix multiplication

There are some procedures:

1. Divide a matrix of order of 2*2 recursively till we get the matrix of 2*2.
2. Use the previous set of formulas to carry out 2*2 matrix multiplication.
3. In this eight multiplication and four additions, subtraction are performed.
4. Combine the result of two matrixes to find the final product or final matrix.

Formulas for Stassen’s matrix multiplication

In Strassen’s matrix multiplication there are seven multiplication and four addition, subtraction in total.

    1. D1 =  (a11 + a22) (b11 + b22)
    2. D2 =  (a21 + a22).b11
    3. D3 =  (b12 – b22).a11
    4. D4 =  (b21 – b11).a22
    5. D5 =  (a11 + a12).b22
    6. D6 =  (a21 – a11) . (b11 + b12)
    7. D7 =  (a12 – a22) . (b21 + b22)

    C11 = d1 + d4 – d5 + d7
    C12 = d3 + d5
    C21 = d2 + d4
    C22 = d1 + d3 – d2 – d6

Algorithm for Strassen’s matrix multiplication

Algorithm Strassen(n, a, b, d)

begin 
 If n = threshold then compute
  C = a * b is a conventional matrix.
 Else
  Partition a into four sub matrices  a11, a12, a21, a22.
  Partition b into four sub matrices b11, b12, b21, b22.
  Strassen ( n/2, a11 + a22, b11 + b22, d1)
  Strassen ( n/2, a21 + a22, b11, d2)
  Strassen ( n/2, a11, b12 – b22, d3)
  Strassen ( n/2, a22, b21 – b11, d4)
  Strassen ( n/2, a11 + a12, b22, d5)
  Strassen (n/2, a21 – a11, b11 + b22, d6)
  Strassen (n/2, a12 – a22, b21 + b22, d7)

  C = d1+d4-d5+d7     d3+d5
  d2+d4           d1+d3-d2-d6  
  
 end if
 
 return (C)
end.

Example :

/* MULTIPLIES A and B =============
 using Strassen's O(n^2.81) method

   A = [1  3]      B = [6  8]
       [7  5]          [4  2]
     
 C = A * B = ?
 =================================*/


// Step 1: Split A and B into half-sized matrices of size 1x1 (scalars).
def a11 = 1
def a12 = 3
def a21 = 7
def a22 = 5
def b11 = 6
def b12 = 8
def b21 = 4
def b22 = 2


// Define the "S" matrix.
def s1 = b12 - b22 // 6
def s2 = a11 + a12 // 4
def s3 = a21 + a22 // 12
def s4 = b21 - b11 // -2
def s5 = a11 + a22 // 6
def s6 = b11 + b22 // 8
def s7 = a12 - a22 // -2
def s8 = b21 + b22 // 6
def s9 = a11 - a21 // -6
def s10 = b11 + b12 // 14


// Define the "P" matrix.
def p1 = a11 * s1 // 6
def p2 = s2 * b22 // 8
def p3 = s3 * b11 // 72
def p4 = a22 * s4 // -10
def p5 = s5 * s6 // 48
def p6 = s7 * s8 // -12
def p7 = s9 * s10 // -84


// Fill in the resultant "C" matrix.
def c11 = p5 + p4 - p2 + p6 // 18
def c12 = p1 + p2 //  14
def c21 = p3 + p4 // 62
def c22 = p5 + p1 - p3 - p7 // 66


/* RESULT: =================

     C = [ 18   14]
         [ 62   66]

=========================*/