I am trying to finish a program that compares the Classical matrix multiplicatio
ID: 3913692 • Letter: I
Question
I am trying to finish a program that compares the Classical matrix multiplication, Divide-and-conquer matrix multiplication, and Strassen's matrix multiplication. In order to obtain more accurate results, the algorithms need to be tested with the same matrices of different sizes many times. The total time spent is then divided by the number of times the algorithm is performed to obtain the time taken to solve the given instance. The matrix size can be n x n. I need the output to have a complete test of all 3 algorithms with n = 2, 4, 8, 16, 32, 64, 128, 256, … (up to the largest size of n that my computer can handle).
Below is what I have already programmed for Classical and Strassen. I did not post Divide and Conquer becuase it is too similar to Strassen's. I need help completing the code so that it will be able to test n sizes so that I can write a report that analyzes all three, and can yield results that I can graph. Please help me generate the time that each algorithm takes to complete n data tests. Thank you, I will thumbs up for a response.
Main Class:
package project_1_main;
import java.util.Random;
import java.util.Scanner;
/**
*
* @author Dragon
*/
public class main {
/**
* @param args
* the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner input = new Scanner(System.in);
StrassenMatrixMultiplication strassenMatixMultiplication = new StrassenMatrixMultiplication();
System.out.println("Enter the base of squared matrices:");
int n = input.nextInt();
int[][] firstMatrix = new int[n][n];
int[][] secondMatrix = new int[n][n];
int[][] finalMatrix = new int[n][n];
Random r = new Random();
int Low = 1;
int High = 10;
System.out.println("Generating first Matrix...");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
firstMatrix[i][j] = r.nextInt(High - Low) + Low;
}
}
System.out.println("Generating second Matrix...");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
secondMatrix[i][j] = r.nextInt(High - Low) + Low;
}
}
finalMatrix = multiply(firstMatrix, secondMatrix); //right here I cannot get the finalMatrix to multiply the 1st and second
System.out.println("Final Matrix is:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(finalMatrix[i][j] + " ");
}
System.out.println();
}
input.close();
}
}
Strassen Matrix Class
package project_1_main;
public class StrassenMatrixMultiplication {
public int[][] multiply(int[][] A, int[][] B) {
int n = A.length;
int[][] R = new int[n][n];
/** base case **/
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);
/**
* M1 = (A11 + A22)(B11 + B22) M2 = (A21 + A22) B11 M3 = A11 (B12 - B22) M4 =
* A22 (B21 - B11) M5 = (A11 + A12) B22 M6 = (A21 - A11) (B11 + B12) M7 = (A12 -
* A22) (B21 + B22)
**/
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));
/**
* C11 = M1 + M4 - M5 + M7 C12 = M3 + M5 C21 = M2 + M4 C22 = M1 - M2 + M3 + M6
**/
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 result **/
return R;
}
/** Funtion to sub two matrices **/
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 into 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];
}
}
Classical Matrix Class
package project_1_main;
import java.util.Random;
import java.util.Scanner;
public class Classical
{
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Enter the base of squared matrices:");
int n = input.nextInt();
int[][] firstMatrix = new int[n][n];
int[][] secondMatrix = new int[n][n];
int[][] finalMatrix = new int[n][n];
Random r = new Random();
int Low = 1;
int High = 10;
System.out.println("Generating first Matrix...");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
firstMatrix[i][j] = r.nextInt(High - Low) + Low;
}
}
System.out.println("Generating second Matrix...");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
secondMatrix[i][j] = r.nextInt(High - Low) + Low;
}
}
System.out.println("Multiplying the matrices...");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
finalMatrix[i][j] = finalMatrix[i][j] + firstMatrix[i][k] * secondMatrix[k][j];
}
}
}
System.out.println("Final Matrix is:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(finalMatrix[i][j] + " ");
}
System.out.println();
}
input.close();
}
}
Explanation / Answer
Hi, i have posted the working codes of strassen's multipplication , classical one and even though you had stated didvide and conqueor is not required , I have tried it and even posted it here , where time is computed for each algorithm when the input is placed.
thank you
1) Strassen's multipication
import java.util.*;
public class strassen
{
public float[][] multiply(float[][] A, float[][] B)
{
int n = A.length;
float[][] R = new float[n][n];
if (n == 1)
R[0][0] = A[0][0] * B[0][0];
else
{
float[][] A11 = new float[n/2][n/2];
float[][] A12 = new float[n/2][n/2];
float[][] A21 = new float[n/2][n/2];
float[][] A22 = new float[n/2][n/2];
float[][] B11 = new float[n/2][n/2];
float[][] B12 = new float[n/2][n/2];
float[][] B21 = new float[n/2][n/2];
float[][] B22 = new float[n/2][n/2];
split(A, A11, 0 , 0);
split(A, A12, 0 , n/2);
split(A, A21, n/2, 0);
split(A, A22, n/2, n/2);
split(B, B11, 0 , 0);
split(B, B12, 0 , n/2);
split(B, B21, n/2, 0);
split(B, B22, n/2, n/2);
float[][] M1 = multiply(add(A11, A22), add(B11, B22));
float[][] M2 = multiply(add(A21, A22), B11);
float[][] M3 = multiply(A11, sub(B12, B22));
float[][] M4 = multiply(A22, sub(B21, B11));
float[][] M5 = multiply(add(A11, A12), B22);
float[][] M6 = multiply(sub(A21, A11), add(B11, B12));
float[][] M7 = multiply(sub(A12, A22), add(B21, B22));
float [][] C11 = add(sub(add(M1, M4), M5), M7);
float [][] C12 = add(M3, M5);
float [][] C21 = add(M2, M4);
float [][] C22 = add(sub(add(M1, M3), M2), M6);
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 float[][] sub(float[][] A, float[][] B)
{
int n = A.length;
float[][] C = new float[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;
}
public float[][] add(float[][] A, float[][] B)
{
int n = A.length;
float[][] C = new float[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;
}
public void split(float[][] P, float[][] 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];
}
public void join(float[][] C, float[][] 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 sn=new Scanner(System.in);
int m;
System.out.println("enter order of matrix");
m=sn.nextInt();
float[][] a = new float[m][m];
float[][] b = new float[m][m];
float c[][]=new float[m][m];
System.out.println("enter matrix A elements");
for(int i=0;i<m;i++)
{//System.out.println();
for(int j=0;j<m;j++)
{
a[i][j]=sn.nextFloat();
//System.out.print(a[i][j]+" ");
}
}
System.out.println("enter matrix B elements");
for(int i=0;i<m;i++)
{//System.out.println();
for(int j=0;j<m;j++)
{
b[i][j]=sn.nextFloat();
//System.out.print(b[i][j]+" ");
}
}
/*Scanner scan = new Scanner(System.in);
System.out.println("Strassen Multiplication Algorithm Test ");
/** Make an object of Strassen class **/
strassen s = new strassen();
final float startTime = System.currentTimeMillis();
float[][] C = s.multiply(a, b);
final float endTime = System.currentTimeMillis();
/* System.out.println(" Product of matrices A and B : ");
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
System.out.print(C[i][j] +" ");
System.out.println();
} */
System.out.println("Total execution time in millisecond: " + (endTime - startTime) );
}
}
2) Classical multiplication
import java.util.*;
public class bruteforce
{
public static void main(String[] args )
{
int m;
Scanner sn=new Scanner(System.in);
System.out.println("enter order of matrix");
m=sn.nextInt();
float[][] a = new float[m][m];
float[][] b = new float[m][m];
float sum = 0;
float[][] c = new float[m][m];
System.out.println("enter matrix A elements");
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
a[i][j]=sn.nextFloat();
}
}
System.out.println("enter matrix b elements");
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
b[i][j]=sn.nextFloat();
}
}
final float startTime = System.currentTimeMillis();
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
for(int k=0;k<m;k++)
{
sum=sum+a[i][k]*b[k][j];
}
c[i][j]=sum;
}
}
final float endTime = System.currentTimeMillis();
System.out.println("Total execution time in millisecond: " + (endTime - startTime) );
}
}
3) divide and conquer
import java.util.*;
public class dividenconq
{
/*public static float[][] matrixMultiplicationFinal(float[][] A, float[][] B){
return matrixMultiplication(
A, B, 0, 0,
0,0, A.length);
}*/
public static float[][] matrixMultiplication(
float[][] A, float[][] B, int rowA, int colA,
int rowB, int colB, int size){
float[][] C= new float[size][size];
if(size==1)
C[0][0]= A[rowA][colA]*B[rowB][colB];
else{
int newSize= size/2;
//C11
sumMatrix(C,
matrixMultiplication(A, B, rowA, colA, rowB, colB, newSize),
matrixMultiplication(A, B, rowA, colA+newSize, rowB+ newSize, colB, newSize),
0, 0);
sumMatrix(C,
matrixMultiplication(A, B, rowA, colA, rowB, colB + newSize, newSize),
matrixMultiplication(A, B, rowA, colA+newSize, rowB+ newSize, colB+newSize, newSize),
0, newSize);
sumMatrix(C,
matrixMultiplication(A, B, rowA+ newSize, colA, rowB, colB, newSize),
matrixMultiplication(A, B, rowA+ newSize, colA+newSize, rowB+ newSize, colB, newSize),
newSize, 0);
sumMatrix(C,
matrixMultiplication(A, B, rowA+ newSize, colA, rowB, colB+newSize, newSize),
matrixMultiplication(A, B, rowA+ newSize, colA+newSize, rowB+ newSize, colB+newSize, newSize),
newSize, newSize);
}
return C;
}
private static void sumMatrix(float[][] C, float[][] A, float[][] B,int rowC, int colC){
int n=A.length;
for(int i =0; i<n; i++)
{
// System.out.println();
for(int j=0; j<n; j++)
{
C[i+rowC][j+colC]=A[i][j]+B[i][j];
// System.out.print(C[i+rowC][j+colC]+ " ");
}
}
}
public static void main(String[] args )
{
int m;
Scanner sn=new Scanner(System.in);
System.out.println("enter order of matrix");
m=sn.nextInt();
float[][] a = new float[m][m];
float[][] b = new float[m][m];
System.out.println("enter matrix A elements");
for(int i=0;i<m;i++)
{//System.out.println();
for(int j=0;j<m;j++)
{
a[i][j]=sn.nextFloat();
//System.out.print(a[i][j]+" ");
}
}
System.out.println("enter matrix B elements");
for(int i=0;i<m;i++)
{//System.out.println();
for(int j=0;j<m;j++)
{
b[i][j]=sn.nextFloat();
//System.out.print(b[i][j]+" ");
}
}
final float startTime = System.currentTimeMillis();
matrixMultiplication(a,b,0,0,0,0,a.length);
final float endTime = System.currentTimeMillis();
System.out.println("Total execution time in millisecond: " + (endTime - startTime) );
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.