Calculation of the matrix determinant

Question

I am trying to compute a matrix determinant (of any size) for a self-coding / interviewing practice. My first attempt at using recursion, and this 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, everything is fine and gives the correct result. Now, I would like to optimize my code using multiple threads to calculate this determining 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 poor, and the higher the matrix size, the slower it becomes (compared to the first approach). Where is the overhead? Can someone shed some light on how to improve this?

Answer 1

The main reason ForkJoin code is slower is because it actually serializes with some streaming threads. To benefit from fork / join, you need to: 1) deploy all instances first, and then 2) wait for the results. Divide your loop into "computation" into two loops: one for fork (saving instances of ParallelDeterminants in, say, an array), and the other for collecting results.

In addition, I propose only to develop at the most external level, and not in any of the internal. You do not want to create 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 its determinant. It can be used for a matrix of high size, for example 500 x 500 or even more. The bright side of this class is that you can get the result in BigDecimal so that there is no infinity, and you always have the exact answer . By the way, using many different methods and avoiding recursion led to a much faster path with higher response performance. hope it will 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 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 own row, so cols must be added addCol(colPos, j); break outer; } if (j == colPos) { // found "!= 0" in it 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 the nxn matrix from the user, and then calculates its determinant. The solution and the final triangular matrix are also shown.

  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; }} 

Answer 3

 int det(int[][] mat, int n) { if (mat.length == 1) return mat[0][0]; if (mat.length == 2) return mat[0][0] * mat[1][1] - mat[1][0] * mat[0][1]; int sum = 0, sign = 1; int newN = mat.length - 1; int[][] temp = new int[newN][newN]; int q = 0, p = 0; for (int i = 0; i < newN; i++) { for (int j = 0; j < newN; j++) { if (p == 0) p = 1; if (q == n) q = 1; temp[i][j] = mat[p + i][q + j]; } } for (int i = 0; i < mat.length - n; i++) { sum += sign * mat[0][n] * det(temp, n + 1); sign *= -1; } return sum; } 

Answer 4

 int det(int[][] mat) { if (mat.length == 1) return mat[0][0]; if (mat.length == 2) return mat[0][0] * mat[1][1] - mat[1][0] * mat[0][1]; int sum = 0, sign = 1; int newN = mat.length - 1; int[][] temp = new int[newN][newN]; for (int t = 0; t < newN; t++) { int q = 0; for (int i = 0; i < newN; i++) { for (int j = 0; j < newN; j++) { temp[i][j] = mat[1 + i][q + j]; } if (q == i) q = 1; } sum += sign * mat[0][t] * det(temp); sign *= -1; } return sum; }