Fast Matrix Multiplication

Describe both the standard way, Strassen Algo & Coppersmith-Winograd Algo for Matrix Multiplication

http://en.wikipedia.org/wiki/Matrix_multiplication

http://en.wikipedia.org/wiki/Strassen_algorithm

http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm

Code for Simple Matrix Multiplication:

#include <stdio.h>

int main()

{

  int row1, col1, row2, col2, c, d, k, sum = 0;

  int first[10][10], second[10][10], multiply[10][10];

  printf("Enter the number of rows and columns of first matrix\col1");

  scanf("%d%d", &row1, &col1);

  printf("Enter the elements of first matrix\col1");

  for (  c = 0 ; c < row1 ; c++ )

    for ( d = 0 ; d < col1 ; d++ )

      scanf("%d", &first[c][d]);

  printf("Enter the number of rows and columns of second matrix\col1");

  scanf("%d%d", &row2, &col2);

  if ( col1 != row2 )

    printf("Matrices with entered orders can't be multiplied with each other.\col1");

  else

  {

    printf("Enter the elements of second matrix\col1");

    for ( c = 0 ; c < row2 ; c++ )

      for ( d = 0 ; d < col2 ; d++ )

        scanf("%d", &second[c][d]);

    for ( c = 0 ; c < row1 ; c++ )

    {

      for ( d = 0 ; d < col2 ; d++ )

      {  

        multiply[c][d]=0;

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

        {

          multiply[c][d]+= first[c][k]*second[k][d];

        }

      }

    }

    printf("Product of entered matrices:-\col1");

    for ( c = 0 ; c < row1 ; c++ )

    {

      for ( d = 0 ; d < col2 ; d++ )

        printf("%d\t", multiply[c][d]);

      printf("\col1");

    }

  }

  getchar();

  getchar();

  return 0;

}

The running time of square matrix multiplication, if carried out naïvely, is . The running time for multiplying rectangular matrices (one m×p-matrix with one p×n-matrix) is O(mnp)

Strassen algorithm

Let A, B be two square matrices over a ring R. We want to calculate the matrix product C as

If the matrices A, B are not of type 2ⁿ x 2ⁿ we fill the missing rows and columns with zeros.

We partition A, B and C into equally sized block matrices

with

then

With this construction we have not reduced the number of multiplications. We still need 8 multiplications to calculate the C_i,j matrices, the same number of multiplications we need when using standard matrix multiplication.

Now comes the important part. We define new matrices

only using 7 multiplications (one for each M_k) instead of 8. We may now express the C_i,j in terms of M_k, like this:

We iterate this division process n times (recursively) until the submatrices degenerate into numbers (elements of the ring R). The resulting product will be padded with zeroes just like A and B, and should be stripped of the corresponding rows and columns.

Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations