Calculating matrix determinant

Question

I am trying to calculate the determinant of a matrix (of any size), for self coding / interview practice. My first attempt is using recursion and that leads me to the following implementation:

import java.util.Scanner.*;
public class Determinant {

    double A[][];
    double m[][];
    int N;
    int start;
    int last;

    public Determinant (double A[][], int N, int start, int last){
            this.A = A;
            this.N = N;
            this.start = start;
            this.last = last;
    }

    public double[][] generateSubArray (double A[][], int N, int j1){
            m = new double[N-1][];
            for (int k=0; k<(N-1); k++)
                    m[k] = new double[N-1];

            for (int i=1; i<N; i++){
                  int j2=0;
                  for (int j=0; j<N; j++){
                      if(j == j1)
                            continue;
                      m[i-1][j2] = A[i][j];
                      j2++;
                  }
              }
            return m;
    }
    /*
     * Calculate determinant recursively
     */
    public double determinant(double A[][], int N){
        double res;

        // Trivial 1x1 matrix
        if (N == 1) res = A[0][0];
        // Trivial 2x2 matrix
        else if (N == 2) res = A[0][0]*A[1][1] - A[1][0]*A[0][1];
        // NxN matrix
        else{
            res=0;
            for (int j1=0; j1<N; j1++){
                 m = generateSubArray (A, N, j1);
                 res += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * determinant(m, N-1);
            }
        }
        return res;
    }
}

So far it is all good and it gives me a correct result. Now I would like to optimise my code by making use of multiple threads to calculate this determinant value. I tried to parallelize it using the Java Fork/Join model. This is my approach:

@Override
protected Double compute() {
     if (N < THRESHOLD) {
         result = computeDeterminant(A, N);
         return result;
     }

     for (int j1 = 0; j1 < N; j1++){
          m = generateSubArray (A, N, j1);
          ParallelDeterminants d = new ParallelDeterminants (m, N-1);
          d.fork();
          result += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * d.join();
     }

     return result;
}

public double computeDeterminant(double A[][], int N){
    double res;

    // Trivial 1x1 matrix
    if (N == 1) res = A[0][0];
    // Trivial 2x2 matrix
    else if (N == 2) res = A[0][0]*A[1][1] - A[1][0]*A[0][1];
    // NxN matrix
    else{
        res=0;
        for (int j1=0; j1<N; j1++){
             m = generateSubArray (A, N, j1);
             res += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * computeDeterminant(m, N-1);
        }
    }
    return res;
}

/*
 * Main function
 */
public static void main(String args[]){
    double res;
    ForkJoinPool pool = new ForkJoinPool();
    ParallelDeterminants d = new ParallelDeterminants();
    d.inputData();
    long starttime=System.nanoTime();
    res = pool.invoke (d);
    long EndTime=System.nanoTime();

    System.out.println("Seq Run = "+ (EndTime-starttime)/100000);
    System.out.println("the determinant valaue is  " + res);
}

However after comparing the performance, I found that the performance of the Fork/Join approach is very bad, and the higher the matrix dimension, the slower it becomes (as compared to the first approach). Where is the overhead? Can anyone shed a light on how to improve this?

Answer 1

The main reason the ForkJoin code is slower is that it's actually serialized with some thread overhead thrown in. To benefit from fork/join, you need to 1) fork all instances first, then 2) wait for the results. Split your loop in "compute" into two loops: one to fork (storing instances of ParallelDeterminants in, say, an array) and another to collect the results.

Also, I suggest to only fork at the outermost level and not in any of the inner ones. You don't want to be creating O(N^2) threads.

Answer 2

Using This class you can calculate the determinant of a matrix with any dimension

This class uses many different methods to make the matrix triangular and then, calculates the determinant of it. It can be used for matrix of high dimension like 500 x 500 or even more. the bright side of the this class is that you can get the result in BigDecimal so there is no infinity and you'll have always the accurate answer. By the way, using many various methods and avoiding recursion resulted in much faster way with higher performance to the answer. hope it would be helpful.

import java.math.BigDecimal;


public class DeterminantCalc {

private double[][] matrix;
private int sign = 1;


DeterminantCalc(double[][] matrix) {
    this.matrix = matrix;
}

public int getSign() {
    return sign;
}

public BigDecimal determinant() {

    BigDecimal deter;
    if (isUpperTriangular() || isLowerTriangular())
        deter = multiplyDiameter().multiply(BigDecimal.valueOf(sign));

    else {
        makeTriangular();
        deter = multiplyDiameter().multiply(BigDecimal.valueOf(sign));

    }
    return deter;
}


/*  receives a matrix and makes it triangular using allowed operations
    on columns and rows
*/
public void makeTriangular() {

    for (int j = 0; j < matrix.length; j++) {
        sortCol(j);
        for (int i = matrix.length - 1; i > j; i--) {
            if (matrix[i][j] == 0)
                continue;

            double x = matrix[i][j];
            double y = matrix[i - 1][j];
            multiplyRow(i, (-y / x));
            addRow(i, i - 1);
            multiplyRow(i, (-x / y));
        }
    }
}


public boolean isUpperTriangular() {

    if (matrix.length < 2)
        return false;

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < i; j++) {
            if (matrix[i][j] != 0)
                return false;

        }

    }
    return true;
}


public boolean isLowerTriangular() {

    if (matrix.length < 2)
        return false;

    for (int j = 0; j < matrix.length; j++) {
        for (int i = 0; j > i; i++) {
            if (matrix[i][j] != 0)
                return false;

        }

    }
    return true;
}


public BigDecimal multiplyDiameter() {

    BigDecimal result = BigDecimal.ONE;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            if (i == j)
                result = result.multiply(BigDecimal.valueOf(matrix[i][j]));

        }

    }
    return result;
}


// when matrix[i][j] = 0 it makes it's value non-zero
public void makeNonZero(int rowPos, int colPos) {

    int len = matrix.length;

    outer:
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            if (matrix[i][j] != 0) {
                if (i == rowPos) { // found "!= 0" in it's own row, so cols must be added
                    addCol(colPos, j);
                    break outer;

                }
                if (j == colPos) { // found "!= 0" in it's own col, so rows must be added
                    addRow(rowPos, i);
                    break outer;
                }
            }
        }
    }
}


//add row1 to row2 and store in row1
public void addRow(int row1, int row2) {

    for (int j = 0; j < matrix.length; j++)
        matrix[row1][j] += matrix[row2][j];
}


//add col1 to col2 and store in col1
public void addCol(int col1, int col2) {

    for (int i = 0; i < matrix.length; i++)
        matrix[i][col1] += matrix[i][col2];
}


//multiply the whole row by num
public void multiplyRow(int row, double num) {

    if (num < 0)
        sign *= -1;


    for (int j = 0; j < matrix.length; j++) {
        matrix[row][j] *= num;
    }
}


//multiply the whole column by num
public void multiplyCol(int col, double num) {

    if (num < 0)
        sign *= -1;

    for (int i = 0; i < matrix.length; i++)
        matrix[i][col] *= num;

}


// sort the cols from the biggest to the lowest value
public void sortCol(int col) {

    for (int i = matrix.length - 1; i >= col; i--) {
        for (int k = matrix.length - 1; k >= col; k--) {
            double tmp1 = matrix[i][col];
            double tmp2 = matrix[k][col];

            if (Math.abs(tmp1) < Math.abs(tmp2))
                replaceRow(i, k);
        }
    }
}


//replace row1 with row2
public void replaceRow(int row1, int row2) {

    if (row1 != row2)
        sign *= -1;

    double[] tempRow = new double[matrix.length];

    for (int j = 0; j < matrix.length; j++) {
        tempRow[j] = matrix[row1][j];
        matrix[row1][j] = matrix[row2][j];
        matrix[row2][j] = tempRow[j];
    }
}


//replace col1 with col2
public void replaceCol(int col1, int col2) {

    if (col1 != col2)
        sign *= -1;

    System.out.printf("replace col%d with col%d, sign = %d%n", col1, col2, sign);
    double[][] tempCol = new double[matrix.length][1];

    for (int i = 0; i < matrix.length; i++) {
        tempCol[i][0] = matrix[i][col1];
        matrix[i][col1] = matrix[i][col2];
        matrix[i][col2] = tempCol[i][0];
    }
} }

This Class Receives a matrix of n x n from the user then calculates it's determinant. It also shows the solution and the final triangular matrix.

 import java.math.BigDecimal;
 import java.text.NumberFormat;
 import java.util.Scanner;


public class DeterminantTest {

public static void main(String[] args) {

    String determinant;

    //generating random numbers
    /*int len = 300;
    SecureRandom random = new SecureRandom();
    double[][] matrix = new double[len][len];

    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            matrix[i][j] = random.nextInt(500);
            System.out.printf("%15.2f", matrix[i][j]);
        }
    }
    System.out.println();*/

    /*double[][] matrix = {
        {1, 5, 2, -2, 3, 2, 5, 1, 0, 5},
        {4, 6, 0, -2, -2, 0, 1, 1, -2, 1},
        {0, 5, 1, 0, 1, -5, -9, 0, 4, 1},
        {2, 3, 5, -1, 2, 2, 0, 4, 5, -1},
        {1, 0, 3, -1, 5, 1, 0, 2, 0, 2},
        {1, 1, 0, -2, 5, 1, 2, 1, 1, 6},
        {1, 0, 1, -1, 1, 1, 0, 1, 1, 1},
        {1, 5, 5, 0, 3, 5, 5, 0, 0, 6},
        {1, -5, 2, -2, 3, 2, 5, 1, 1, 5},
        {1, 5, -2, -2, 3, 1, 5, 0, 0, 1}
    };
    */

    double[][] matrix = menu();

    DeterminantCalc deter = new DeterminantCalc(matrix);

    BigDecimal det = deter.determinant();

    determinant = NumberFormat.getInstance().format(det);

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            System.out.printf("%15.2f", matrix[i][j]);
        }
        System.out.println();
    }

    System.out.println();
    System.out.printf("%s%s%n", "Determinant: ", determinant);
    System.out.printf("%s%d", "sign: ", deter.getSign());

}


public static double[][] menu() {

    Scanner scanner = new Scanner(System.in);

    System.out.print("Matrix Dimension: ");
    int dim = scanner.nextInt();

    double[][] inputMatrix = new double[dim][dim];

    System.out.println("Set the Matrix: ");
    for (int i = 0; i < dim; i++) {
        System.out.printf("%5s%d%n", "row", i + 1);
        for (int j = 0; j < dim; j++) {

            System.out.printf("M[%d][%d] = ", i + 1, j + 1);
            inputMatrix[i][j] = scanner.nextDouble();
        }
        System.out.println();
    }
    scanner.close();

    return inputMatrix;
}}