0

I'm trying to implement Callable for Strassen's algorithm to multiply two matrices. I'm new to this, and i'm having a few issues and I can't figure it out for the life of me :( .

The first problem is that the program prints out 0 for all the elements of the resultant matrix. For example, if my n (size of matrices to be multiplied) is 4, i get a 4x4 resultant matrix with 0 as all the elements. Second thing is, my execution time increases as I increase the number of threads. Below is my code.

package strassen2;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.Callable;
import java.io.*;
import java.util.concurrent.ExecutionException;

/**
 *
 * @author Subhaa
 */
public  class Strassen2 implements Callable<int[][]>
{
    private  int[][] A;
    private  int[][] B;
    private  int n;
    private int C[][] = new int [n][n];

    public Strassen2 (int A[][], int B[][])
    {
        this.A = A;
        this.B = B;
        this.n = n;
        this.C = C;
    }

   @Override
   public int[][] call() throws Exception
   {

       if(A.length <= 2)
       {
       for (int i = 0 ; i < n ; i++)
       {
           for (int j = 0 ; j < n ; j++)
           {
               for (int k = 0 ; k < n ; k++)
               {
                    C[i][j] = A[i][k] * B[k][j];
               }
           }
       }
       }
       else
           strassenMatrixMultiplication(A,B);
       return C;
   }

    ExecutorService executor = Executors.newFixedThreadPool (4);

    public Strassen2() throws IOException, InterruptedException, ExecutionException
    {
        int n;
        int[][] a, b, c;

        n = 4; // Set size of matrices
        a = new int[n][n];
        b = new int[n][n];
        c = new int[n][n];

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                a[i][j] = 1;
            }
        }

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {

                b[i][j] = 1;

            }
        }

        long start_time = System.nanoTime();

        c = strassenMatrixMultiplication(a,b);

        long end_time = System.nanoTime();
        double difference = (end_time - start_time)/1e6;

        printArray(c);

        System.out.println("Time taken : " + difference);
                executor.shutdown();
                System.exit(0);

    }

    public int [][] strassenMatrixMultiplication(int [][] A, int [][] B) throws InterruptedException, ExecutionException
    {
        int n = A.length;
        int [][] result = new int[n][n];
        if((n%2 != 0 ) && (n !=1))
        {
            int[][] a1, b1, c1;
            int n1 = n+1;
            a1 = new int[n1][n1];
            b1 = new int[n1][n1];
            c1 = new int[n1][n1];
            for(int i=0; i<n; i++)
                for(int j=0; j<n; j++)
                {
                     a1[i][j] =A[i][j];
                     b1[i][j] =B[i][j];
                }

                c1 = strassenMatrixMultiplication(a1, b1);
                for(int i=0; i<n; i++)
                    for(int j=0; j<n; j++)
                        result[i][j] =c1[i][j];
                    return result;
        }
        if(n == 1)
        {
            result[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];

        divideArray(A, A11, 0 , 0);
        divideArray(A, A12, 0 , n/2);
        divideArray(A, A21, n/2, 0);
        divideArray(A, A22, n/2, n/2);
        divideArray(B, B11, 0 , 0);
        divideArray(B, B12, 0 , n/2);
        divideArray(B, B21, n/2, 0);
        divideArray(B, B22, n/2, n/2);

        Future<int[][]> future1;
        Future<int[][]> future2;
        Future<int[][]> future3;
        Future<int[][]> future4;
        Future<int[][]> future5;
        Future<int[][]> future6;
        Future<int[][]> future7;

            int [][] P1 = null ;
            int [][] P2= null ;
            int [][] P3 = null;
            int [][] P4 = null;
            int [][] P5 = null;
            int [][] P6 = null;
            int [][] P7 = null;

        future1 = executor.submit(new Strassen2(addMatrices(A11, A22), addMatrices(B11, B22)));
        future2 = executor.submit(new Strassen2(addMatrices(A21, A22), B11));
        future3 = executor.submit(new Strassen2(A11, subtractMatrices(B12, B22)));
        future4 = executor.submit(new Strassen2(A22, subtractMatrices(B21, B11)));
        future5 = executor.submit(new Strassen2(addMatrices(A11, A12), B22));
        future6 = executor.submit(new Strassen2(subtractMatrices(A21, A11), addMatrices(B11, B12)));
        future7 = executor.submit(new Strassen2(subtractMatrices(A12, A22), addMatrices(B21, B22)));

        P1 = future1.get();
        P2 = future2.get();
        P3 = future3.get();
        P4 = future4.get();
        P5 = future5.get();
        P6 = future6.get();
        P7 = future7.get();

        int [][] C11 = addMatrices(subtractMatrices(addMatrices(P1, P4), P5), P7);           
        int [][] C12 = addMatrices(P3, P5);
        int [][] C21 = addMatrices(P2, P4);
        int [][] C22 = addMatrices(subtractMatrices(addMatrices(P1, P3), P2), P6);

        copySubArray(C11, result, 0 , 0);
        copySubArray(C12, result, 0 , n/2);
        copySubArray(C21, result, n/2, 0);
        copySubArray(C22, result, n/2, n/2);
    }
    return result;
}

    public int [][] addMatrices(int [][] A, int [][] B)
    {
        int n = A.length;
        int [][] result = new int[n][n];
        for(int i=0; i<n; i++)

            for(int j=0; j<n; j++)

                result[i][j] = A[i][j] + B[i][j];

         return result;
    }

    public int [][] subtractMatrices(int [][] A, int [][] B)
    {
        int n = A.length;
        int [][] result = new int[n][n];
        for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        result[i][j] = A[i][j] - B[i][j];
        return result;
    }

    public void divideArray(int[][] parent, int[][] child, int iB, int jB)
    {
        for(int i1 = 0, i2=iB; i1<child.length; i1++, i2++)
        {
            for(int j1 = 0, j2=jB; j1<child.length; j1++, j2++)
            {
                child[i1][j1] = parent[i2][j2];
            }
        }

    }

    public void copySubArray(int[][] child, int[][] parent, int iB, int jB)
    {
        for(int i1 = 0, i2=iB; i1<child.length; i1++, i2++)
        for(int j1 = 0, j2=jB; j1<child.length; j1++, j2++)
        {
            parent[i2][j2] = child[i1][j1];
        }
    }

    public void printArray(int [][] array)
    {
        int n = array.length;
        System.out.println();
        for(int i=0; i<n; i++)
        {
         for(int j=0; j<n; j++)
            {
             System.out.print(array[i][j] + "\t");
            }
           System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException, InterruptedException, ExecutionException 
    {
         new Strassen2();
    }

}
3
Contributors
3
Replies
24
Views
5 Months
Discussion Span
Last Post by JamesCherrill
0

If you look at the call()

else
    strassenMatrixMultiplication(A,B);
return C;

Nothing is being done with the result of strassenMatrixMultiplication(A,B).

All your P# = future#.get()'s are 0.

A few general remarks:

  • Variable names should be lower case in Java, uppercase implies Objects.
  • Always use { and } in if/else statements and loops to improve readability and avoiding mistakes, even if it's only one line.
  • When you have to declare 7 different P's you're probably hard coding too much (and should use collections), although in this particular case it might make it easier to follow. Keep it in mind though.

Edited by Traevel: I need to learn to finish my senten... ooh shiny

0

Oh thank you! I assigned the result of strassenMatrixMultiplication(A,B) to C. But i'm still getting zeroes. Also, any idea why this implementation of Strassen's algorithm is much slower than a naive algorithm like ijk-algorithm?

1

With 4x4 matrices I'm surprised you can even measure execution time meaningfully. I'm not surprised that the overheads of a thread pool would greatly exceed the time to do a few array maipulations. I guess each thread will complete within its first time slice.

Edited by JamesCherrill

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.