Java Program to Implement Strassen 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. }

advertisement
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.

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter