# 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 = A * B;`
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. 