Implement Strassen’s matrix multiplication algorithm. Your program should take a

Question

Implement Strassen’s matrix multiplication algorithm. Your program should take an input variable n (=2k where k is a positive integer) in the Linux command line and generate two n*n random integer matrices, A and B. Compute A*B using Strassen’s algorithm and compare the result to the result produced by the standard matrix multiplication algorithm with O(n3) time complexity. Print the results, if correct. (If incorrect results are produced, no credit will be given. Your program should work for any matrices. If it works for specific matrices but doesn’t work for other matrices, no credit will be given.) Finally, save your source code in a file and name the file as yourlastname_ yourfirstname_pa2_strassen.cpp.

Explanation / Answer

The code consists of Strassen's matrix multilication for 2X2 matrix in C and for nXn matrix using Java. Both the codes were given, please observe once.

#include<stdio.h>
int main()
{
   int a[2][2], b[2][2], c[2][2], i, j;
   int m1, m2, m3, m4 , m5, m6, m7;

   printf("Enter the 4 elements of first matrix: ");
   for(i = 0;i < 2; i++)
       for(j = 0;j < 2; j++)
           scanf("%d", &a[i][j]);

   printf("Enter the 4 elements of second matrix: ");
   for(i = 0; i < 2; i++)
       for(j = 0;j < 2; j++)
           scanf("%d", &b[i][j]);

   printf(" The first matrix is ");
   for(i = 0; i < 2; i++)
   {
       printf(" ");
       for(j = 0; j < 2; j++)
           printf("%d ", a[i][j]);
   }

   printf(" The second matrix is ");
   for(i = 0;i < 2; i++)
   {
       printf(" ");
       for(j = 0;j < 2; j++)
           printf("%d ", b[i][j]);
   }

   m1= (a[0][0] + a[1][1]) * (b[0][0] + b[1][1]);
   m2= (a[1][0] + a[1][1]) * b[0][0];
   m3= a[0][0] * (b[0][1] - b[1][1]);
   m4= a[1][1] * (b[1][0] - b[0][0]);
   m5= (a[0][0] + a[0][1]) * b[1][1];
   m6= (a[1][0] - a[0][0]) * (b[0][0]+b[0][1]);
   m7= (a[0][1] - a[1][1]) * (b[1][0]+b[1][1]);

   c[0][0] = m1 + m4- m5 + m7;
   c[0][1] = m3 + m5;
   c[1][0] = m2 + m4;
   c[1][1] = m1 - m2 + m3 + m6;

   printf(" After multiplication using Strassen's algorithm ");
   for(i = 0; i < 2 ; i++)
   {
       printf(" ");
       for(j = 0;j < 2; j++)
           printf("%d ", c[i][j]);
   }
   return 0;
}

This is an exact java code for the Strassen's matrix multiplication of nXn matrix.

import java.util.Scanner;

public class Strassen
{
public int[][] multiply(int[][] A, int[][] B)
{
int n = A.length;
int[][] R = new int[n][n];
if (n == 1)
R[0][0] = A[0][0] * B[0][0];
else
{
int[][] A11 = new int[n/2][n/2];
int[][] A12 = new int[n/2][n/2];
int[][] A21 = new int[n/2][n/2];
int[][] A22 = new int[n/2][n/2];
int[][] B11 = new int[n/2][n/2];
int[][] B12 = new int[n/2][n/2];
int[][] B21 = new int[n/2][n/2];
int[][] B22 = new int[n/2][n/2];

/** Dividing matrix A into 4 halves **/
split(A, A11, 0 , 0);
split(A, A12, 0 , n/2);
split(A, A21, n/2, 0);
split(A, A22, n/2, n/2);
/** Dividing matrix B into 4 halves **/
split(B, B11, 0 , 0);
split(B, B12, 0 , n/2);
split(B, B21, n/2, 0);
split(B, B22, n/2, n/2);

int [][] M1 = multiply(add(A11, A22), add(B11, B22));
int [][] M2 = multiply(add(A21, A22), B11);
int [][] M3 = multiply(A11, sub(B12, B22));
int [][] M4 = multiply(A22, sub(B21, B11));
int [][] M5 = multiply(add(A11, A12), B22);
int [][] M6 = multiply(sub(A21, A11), add(B11, B12));
int [][] M7 = multiply(sub(A12, A22), add(B21, B22));

int [][] C11 = add(sub(add(M1, M4), M5), M7);
int [][] C12 = add(M3, M5);
int [][] C21 = add(M2, M4);
int [][] C22 = add(sub(add(M1, M3), M2), M6);

/** join 4 halves into one result matrix **/
join(C11, R, 0 , 0);
join(C12, R, 0 , n/2);
join(C21, R, n/2, 0);
join(C22, R, n/2, n/2);
}
return R;
}

public int[][] sub(int[][] A, int[][] B)
{
int n = A.length;
int[][] C = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = A[i][j] - B[i][j];
return C;
}
/** Funtion to add two matrices **/
public int[][] add(int[][] A, int[][] B)
{
int n = A.length;
int[][] C = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = A[i][j] + B[i][j];
return C;
}
/** Funtion to split parent matrix into child matrices **/
public void split(int[][] P, int[][] C, int iB, int jB)
{
for(int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
for(int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++)
C[i1][j1] = P[i2][j2];
}
/** Funtion to join child matrices intp parent matrix **/
public void join(int[][] C, int[][] P, int iB, int jB)
{
for(int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
for(int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++)
P[i2][j2] = C[i1][j1];
}

public static void main (String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Strassen Multiplication Algorithm Test ");
Strassen s = new Strassen();

System.out.println("Enter order n :");
int N = scan.nextInt();
System.out.println("Enter N order matrix 1 ");
int[][] A = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
A[i][j] = scan.nextInt();

System.out.println("Enter N order matrix 2 ");
int[][] B = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
B[i][j] = scan.nextInt();

int[][] C = s.multiply(A, B);

System.out.println(" Product of matrices A and B : ");
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(C[i][j] +" ");
System.out.println();
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.