Java Program to Implement Strassen’s Algorithm

This is a Java Program to Implement Strassen Matrix Multiplication Algorithm. This is a program to compute product of two matrices using Strassen Multiplication algorithm. Here the dimensions of matrices must be a power of 2.

Here is the source code of the Java Program to Implement Strassen Matrix Multiplication Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to Implement Strassen Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class Strassen **/
  8. public class Strassen
  9. {
  10.     /** Function to multiply matrices **/
  11.     public int[][] multiply(int[][] A, int[][] B)
  12.     {        
  13.         int n = A.length;
  14.         int[][] R = new int[n][n];
  15.         /** base case **/
  16.         if (n == 1)
  17.             R[0][0] = A[0][0] * B[0][0];
  18.         else
  19.         {
  20.             int[][] A11 = new int[n/2][n/2];
  21.             int[][] A12 = new int[n/2][n/2];
  22.             int[][] A21 = new int[n/2][n/2];
  23.             int[][] A22 = new int[n/2][n/2];
  24.             int[][] B11 = new int[n/2][n/2];
  25.             int[][] B12 = new int[n/2][n/2];
  26.             int[][] B21 = new int[n/2][n/2];
  27.             int[][] B22 = new int[n/2][n/2];
  28.  
  29.             /** Dividing matrix A into 4 halves **/
  30.             split(A, A11, 0 , 0);
  31.             split(A, A12, 0 , n/2);
  32.             split(A, A21, n/2, 0);
  33.             split(A, A22, n/2, n/2);
  34.             /** Dividing matrix B into 4 halves **/
  35.             split(B, B11, 0 , 0);
  36.             split(B, B12, 0 , n/2);
  37.             split(B, B21, n/2, 0);
  38.             split(B, B22, n/2, n/2);
  39.  
  40.             /** 
  41.               M1 = (A11 + A22)(B11 + B22)
  42.               M2 = (A21 + A22) B11
  43.               M3 = A11 (B12 - B22)
  44.               M4 = A22 (B21 - B11)
  45.               M5 = (A11 + A12) B22
  46.               M6 = (A21 - A11) (B11 + B12)
  47.               M7 = (A12 - A22) (B21 + B22)
  48.             **/
  49.  
  50.             int [][] M1 = multiply(add(A11, A22), add(B11, B22));
  51.             int [][] M2 = multiply(add(A21, A22), B11);
  52.             int [][] M3 = multiply(A11, sub(B12, B22));
  53.             int [][] M4 = multiply(A22, sub(B21, B11));
  54.             int [][] M5 = multiply(add(A11, A12), B22);
  55.             int [][] M6 = multiply(sub(A21, A11), add(B11, B12));
  56.             int [][] M7 = multiply(sub(A12, A22), add(B21, B22));
  57.  
  58.             /**
  59.               C11 = M1 + M4 - M5 + M7
  60.               C12 = M3 + M5
  61.               C21 = M2 + M4
  62.               C22 = M1 - M2 + M3 + M6
  63.             **/
  64.             int [][] C11 = add(sub(add(M1, M4), M5), M7);
  65.             int [][] C12 = add(M3, M5);
  66.             int [][] C21 = add(M2, M4);
  67.             int [][] C22 = add(sub(add(M1, M3), M2), M6);
  68.  
  69.             /** join 4 halves into one result matrix **/
  70.             join(C11, R, 0 , 0);
  71.             join(C12, R, 0 , n/2);
  72.             join(C21, R, n/2, 0);
  73.             join(C22, R, n/2, n/2);
  74.         }
  75.         /** return result **/    
  76.         return R;
  77.     }
  78.     /** Funtion to sub two matrices **/
  79.     public int[][] sub(int[][] A, int[][] B)
  80.     {
  81.         int n = A.length;
  82.         int[][] C = new int[n][n];
  83.         for (int i = 0; i < n; i++)
  84.             for (int j = 0; j < n; j++)
  85.                 C[i][j] = A[i][j] - B[i][j];
  86.         return C;
  87.     }
  88.     /** Funtion to add two matrices **/
  89.     public int[][] add(int[][] A, int[][] B)
  90.     {
  91.         int n = A.length;
  92.         int[][] C = new int[n][n];
  93.         for (int i = 0; i < n; i++)
  94.             for (int j = 0; j < n; j++)
  95.                 C[i][j] = A[i][j] + B[i][j];
  96.         return C;
  97.     }
  98.     /** Funtion to split parent matrix into child matrices **/
  99.     public void split(int[][] P, int[][] C, int iB, int jB) 
  100.     {
  101.         for(int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
  102.             for(int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++)
  103.                 C[i1][j1] = P[i2][j2];
  104.     }
  105.     /** Funtion to join child matrices intp parent matrix **/
  106.     public void join(int[][] C, int[][] P, int iB, int jB) 
  107.     {
  108.         for(int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
  109.             for(int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++)
  110.                 P[i2][j2] = C[i1][j1];
  111.     }    
  112.     /** Main function **/
  113.     public static void main (String[] args) 
  114.     {
  115.         Scanner scan = new Scanner(System.in);
  116.         System.out.println("Strassen Multiplication Algorithm Test\n");
  117.         /** Make an object of Strassen class **/
  118.         Strassen s = new Strassen();
  119.  
  120.         System.out.println("Enter order n :");
  121.         int N = scan.nextInt();
  122.         /** Accept two 2d matrices **/
  123.         System.out.println("Enter N order matrix 1\n");
  124.         int[][] A = new int[N][N];
  125.         for (int i = 0; i < N; i++)
  126.             for (int j = 0; j < N; j++)
  127.                 A[i][j] = scan.nextInt();
  128.  
  129.         System.out.println("Enter N order matrix 2\n");
  130.         int[][] B = new int[N][N];
  131.         for (int i = 0; i < N; i++)
  132.             for (int j = 0; j < N; j++)
  133.                 B[i][j] = scan.nextInt();
  134.  
  135.         int[][] C = s.multiply(A, B);
  136.  
  137.         System.out.println("\nProduct of matrices A and  B : ");
  138.         for (int i = 0; i < N; i++)
  139.         {
  140.             for (int j = 0; j < N; j++)
  141.                 System.out.print(C[i][j] +" ");
  142.             System.out.println();
  143.         }
  144.  
  145.     }
  146. }

Strassen Multiplication Algorithm Test
 
Enter order n :
4
Enter N order matrix 1
 
2 3 1 6
4 0 0 2
4 2 0 1
0 3 5 2
Enter N order matrix 2
 
3 0 4 3
1 2 0 2
0 3 1 4
5 1 3 2
 
Product of matrices A and  B :
39 15 27 28
22 2 22 16
19 5 19 18
13 23 11 30

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.