Java inverse matrix calculation

Question

I'm trying to calculate the inverse matrix in Java.

I'm following the adjoint method (first calculation of the adjoint matrix, then transpose this matrix and finally, multiply it for the inverse of the value of the determinant).

It works when the matrix is not too big. I've checked that for matrixes up to a size of 12x12 the result is quickly provided. However, when the matrix is bigger than 12x12 the time it needs to complete the calculation increases exponentially.

The matrix I need to invert is 19x19, and it takes too much time. The method that more time consumes is the method used for the calculation of the determinant.

The code I'm using is:

public static double determinant(double[][] input) {
  int rows = nRows(input);        //number of rows in the matrix
  int columns = nColumns(input); //number of columns in the matrix
  double determinant = 0;

  if ((rows== 1) && (columns == 1)) return input[0][0];

  int sign = 1;     
  for (int column = 0; column < columns; column++) {
    double[][] submatrix = getSubmatrix(input, rows, columns,column);
    determinant = determinant + sign*input[0][column]*determinant(submatrix);
    sign*=-1;
  }
  return determinant;
}

Does anybody know how to calculate the determinant of a large matrix more efficiently? If not, does anyone knows how to calcultate the inverse of a large matrix using other algorithm?

Thanks

@duffymo: thanks for your answer. You're right, not exponentially, what I mean is that from matrix size 12x12 the time it takes to compute the determinant increases spectacularly. I've tried Jama, but I don't get it to work (I'm pretty new in Java). I'll also look into LU descomposition. Thanks. — dedalo
No, "exponentially" is correct, as your algorithm is indeed exponential, but duffymo is also correct in that matrix inversion or determinant computation do not require exponential time. — JaakkoK
Thanks to all. I've looking at Jama and I found the method 'det' in the class Matrix that calculates it quickly. I also found methods to calculate the matrix L and U (A = LU) and then det(A) = det(L) det(U). — dedalo

duffymo duffymo · Accepted Answer · 2010-01-02T19:59:06

Exponentially? No, I believe matrix inversion is O(N^3).

I would recommend using LU decomposition to solve a matrix equation. You don't have to solve for the determinant when you use it.

Better yet, look into a package to help you. JAMA comes to mind.

12x12 or 19x19 are not large matricies. It's common to solve problems with tens or hundreds of thousands of degrees of freedom.

Here's a working example of how to use JAMA. You have to have the JAMA JAR in your CLASSPATH when you compile and run:

package linearalgebra;

import Jama.LUDecomposition;
import Jama.Matrix;

public class JamaDemo
{
    public static void main(String[] args)
    {
        double [][] values = {{1, 1, 2}, {2, 4, -3}, {3, 6, -5}};  // each array is a row in the matrix
        double [] rhs = { 9, 1, 0 }; // rhs vector
        double [] answer = { 1, 2, 3 }; // this is the answer that you should get.

        Matrix a = new Matrix(values);
        a.print(10, 2);
        LUDecomposition luDecomposition = new LUDecomposition(a);
        luDecomposition.getL().print(10, 2); // lower matrix
        luDecomposition.getU().print(10, 2); // upper matrix

        Matrix b = new Matrix(rhs, rhs.length);
        Matrix x = luDecomposition.solve(b); // solve Ax = b for the unknown vector x
        x.print(10, 2); // print the solution
        Matrix residual = a.times(x).minus(b); // calculate the residual error
        double rnorm = residual.normInf(); // get the max error (yes, it's very small)
        System.out.println("residual: " + rnorm);
    }
}

Here's the same problem solved using Apache Commons Math, per quant_dev's recommendation:

package linearalgebra;

import org.apache.commons.math.linear.Array2DRowRealMatrix;
import org.apache.commons.math.linear.ArrayRealVector;
import org.apache.commons.math.linear.DecompositionSolver;
import org.apache.commons.math.linear.LUDecompositionImpl;
import org.apache.commons.math.linear.RealMatrix;
import org.apache.commons.math.linear.RealVector;

public class LinearAlgebraDemo
{
    public static void main(String[] args)
    {
        double [][] values = {{1, 1, 2}, {2, 4, -3}, {3, 6, -5}};
        double [] rhs = { 9, 1, 0 };

        RealMatrix a = new Array2DRowRealMatrix(values);
        System.out.println("a matrix: " + a);
        DecompositionSolver solver = new LUDecompositionImpl(a).getSolver();

        RealVector b = new ArrayRealVector(rhs);
        RealVector x = solver.solve(b);
        System.out.println("solution x: " + x);;
        RealVector residual = a.operate(x).subtract(b);
        double rnorm = residual.getLInfNorm();
        System.out.println("residual: " + rnorm);
    }
}

Adapt these to your situation.

Java inverse matrix calculation

11 Answers