Gaussian Elimination in Java

Question

I was trying to implement a Matrix.class to learn some Java. Right now, I have some difficulties with a method that should return the matrix after Gaussian elimination which will be used to find the inverse of a matrix later on.
Here is what I came up with so far:

public Matrix gaussianElimination() {
    Matrix inv = this.clone();
    int i = 0;
    int j = 0;

    while (i<inv.getHeight() && j<inv.getWidth()) {
        int pivot = i;
        for (int k=i+1; k<inv.getHeight(); k++) {
            if (Math.abs(inv.getArray()[k][j]) > Math.abs(inv.getArray()[pivot][j])) {
                pivot = k;
            }
        }
        if (inv.getArray()[pivot][j] != 0) {
            inv = inv.swapRow(i, pivot);
            double div = inv.getArray()[i][j];
            for (double value : inv.getArray()[i]) {
                value = value/div;
            }
            for (int u=i+1; u < inv.getHeight(); u++) {
                double mult = inv.getArray()[u][j];
                for (int l=0; l<inv.getWidth(); l++) {
                    inv.getArray()[u][l] = mult * inv.getArray()[i][l];
                }
            }
        }
        j++;
        i++;
    }
    return inv;
}

Whereas the getArray() function returns the double[][] of the matrix, getHeight() and getWidth() return inv.length and inv[0].length respectably.

I followed the pseudocode of this wikipedia page to implement the algorithm.
The method returns a matrix with line of the first pivot element on top but does not calculate the lower rows correctly.

For instance:

A
0.2635522849474877 0.10001114673002853 0.442971040143471
0.2986277338922876 0.7517642579959294 0.09150190333830721
0.8913610667753092 0.8898546572478708 0.25592546060133237

Inv
0.8913610667753092 0.8898546572478708 0.25592546060133237
0.26618513545092265 0.26573527978742995 0.07642644034471581
0.062426597261833985 0.06232109565941264 0.017923775508624545

I would be very thankful for any help as I can't find a solution. I've probably mixed a pointer somewhere or implemented the algorithm wrong.

Dave Costa Dave Costa · Accepted Answer · 2011-03-03T13:49:03

I see two problems.

In these lines:

        for (double value : inv.getArray()[i]) {
            value = value/div;
        }

you aren't modifying the values stored in the matrix; you're simply modifying the value of value then discarding it. You want something like:

for (int idx=0; idx<inv.getWidth(); idx++) {
  inv.getArray()[i,idx] = inv.getArray()[i,idx] / div;
}

Also, in this line:

inv.getArray()[u][l] = mult * inv.getArray()[i][l];

You should change = to -=. The algorithm says "subtract A[u,j] * row i from row u". You are simply replacing the values in row u with the product.

Gaussian Elimination in Java

1 Answers