Java optimized Cramers rule function

Question 1

First of, there is one way in which Cramers rule is perfect: It gives the algebraic solution of a linear system as a rational function in its coefficients.

However, practically, it has its limits. While the most perfect formula for a 2x2 system, and still good for a 3x3 system, its performance, if implemented in the straightforward way, deteriorates with each additional dimension.

An almost literal implementation of Cramers rule can be achieved with the Leverrier-Faddeev algorithm ^{a b}. It only requires the computation of matrix products and matrix traces, and manipulations of the matrix diagonal. Not only does it compute the determinant of the matrix A (along with the other coefficients of the characteristic polynomial), it also has the adjugate or co-factor matrix A^# in its iteration matrix. The interesting fact about this matrix is that it allows to write the solution of A*x=b as (A^#*b)/det(A), that is, the entries of A^#*b already are the other determinants required by Cramers rule.

Leverrier-Faddeev requires n⁴+O(n³) operations. The same results can be obtained by the more complicated Samuelson-Berkowitz algorith, which has one third of that complexity, that is n⁴/3+O(n³).

The computation of the determinants required in Cramers rule becomes downright trivial if the system (A|b) is first transformed into triangular form. That can be achieved by Gauß elimination, aka LU decomposition (with pivoting for numerical stability) or the QR decomposition (easiest to debug should be the variant with Givens rotations). The efficient application of Cramers rule is then backward substitution in the triangular system.

Question 2

Your method sounds good to me at least; however, I just may not be aware of any more efficient methods. The not-fun part may be figuring out how to best implement the determinant-calculating method, as apparently it's not an inexpensive operation.

But once you know that that's working, the rest sounds pretty OK to me. Cache the determinant of the original matrix, substitute in columns, etc.

Question 3

Figured out exactly how to do this effectively.

http://sandsduchon.org/duchon/math/determinantJava.html

Provides a method for seamless determinants, and mentions matrix decomposition. I have not learned this yet as it's not a HS level concept however I did some problems using it and it's a solid method.

Final Code:

    public static void main(String[] args) {
        int[][] matrix = new int[3][3];
        matrix[0] = new int[] { 3, 5, -1, -2 };
        matrix[1] = new int[] { 1, -4, 2, 13 };
        matrix[2] = new int[] { 2, 4, 3, 1 };
        int[] r = crame(matrix);
        info("x: " + r[0] + ", y: " + r[1] + ", z: " + r[2]);
        for (int i = 0; i < matrix.length; i++) {
          int[] base = matrix[i];
          if (check(base, r, base[3])) {
             info("System " + (i + 1) + " checks!");
          } else {
             info("System " + (i + 1) + " fails check!");
        }
    }
}

public static int getDet(int[][] a) {
    int n = a.length - 1;
    if (n < 0)
        return 0;
    int M[][][] = new int[n + 1][][];
    M[n] = a; // init first, largest, M to a
    // create working arrays
    for (int i = 0; i < n; i++)
        M[i] = new int[i + 1][i + 1];
    return getDet(M, n);
} // end method getDecDet double [][] parameter

public static int getDet(int[][][] M, int m) {
    if (m == 0)
        return M[0][0][0];
    int e = 1;
    // init subarray to upper left mxm submatrix
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            M[m - 1][i][j] = M[m][i][j];
    int sum = M[m][m][m] * getDet(M, m - 1);
    // walk through rest of rows of M
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 0; j < m; j++)
            M[m - 1][i][j] = M[m][i + 1][j];
        e = -e;
        sum += e * M[m][i][m] * getDet(M, m - 1);
    } // end for each row of matrix
    return sum;
} // end getDecDet double [][][], int

public static int[] crame(int[][] m) {
    int[] result;
    if (m.length == 2) {
        result = new int[m.length];
        int D = getDet(m);
        for (int i = 0; i < m.length; i++) {
            result[i] = getDet(slide(m, i, m.length)) / D;
        }
    } else if (m.length == 3) {
        result = new int[m.length];
        int D = getDet(m);
        for (int i = 0; i < m.length; i++) {
            result[i] = (getDet(slide(m, i, m.length)) / D);
        }
    } else {
        return new int[] {};
    }
    return result;
}

public static int[][] slide(int[][] base, int col, int fin) {
    int[][] copy = new int[base.length][];
    for (int i = 0; i < base.length; i++) {
        int[] aMatrix = base[i];
        int aLength = aMatrix.length;
        copy[i] = new int[aLength];
        System.arraycopy(aMatrix, 0, copy[i], 0, aLength);
    }
    for (int i = 0; i < base.length; i++) {
        copy[i][col] = base[i][fin];
    }
    return copy;
}

public static int product(int[] a, int[] b) {
    int p = 0;
    int[] fin = new int[(a.length - 1)];
    for (int x = 0; x < fin.length; x++) {
        fin[x] = a[x] * b[x];
    }
    for (int f : fin) {
        p += f;
    }
    return p;
}

public static boolean check(int[] a, int[] b, int z) {
    return product(a, b) == z;
}

public static void info(String log) {
    System.out.println(log);
}