Performing Gauss-Jordan elimination on a matrix in Java

I have this small "framework" for representing matrices with entries of primitive type double, and performing Gauss-Jordan elimination (for solving systems of linear equations). My main concern is cohesion of my code, but I would be glad to hear whatever comes to mind.

GaussJordanElimination.java:

package net.coderodde.math.linear;

import static net.coderodde.math.linear.Utils.checkNotInfinite;
import static net.coderodde.math.linear.Utils.checkNotNaN;
import static net.coderodde.math.linear.Utils.checkNotNegative;
import static net.coderodde.math.linear.Utils.checkNotNull;

/**
* This class provides a static method performing Gauss-Jordan elimination on an
* input matrix.
*/
public class GaussJordanElimination {

/**
* Defines the default epsilon for comparison.
*/
private static final double DEFAULT_EPSILON = 1E-6;

/**
* Defines the sentinel value for any index of a non-valid row.
*/
private static final int ROW_NOT_FOUND = -1;

/**
* Caches the actual matrix.
*/
private final double[][] m;

/**
* The epsilon value for comparisons.
*/
private final double epsilon;

/**
* Performs Gauss-Jordan elimination on the input matrix using given
* epsilon.
*
* @param matrix  the matrix to eliminate.
* @param epsilon the epsilon value used for comparisons.
* @return        the rank of the resulting matrix.
*/
public static int solve(final Matrix matrix, final double epsilon) {
return new GaussJordanElimination(matrix.m, epsilon).eliminate();
}

/**
* Performs Gauss-Jordan elimination on the input matrix using default
* epsilon.
*
* @param matrix the matrix to eliminate.
* @return       the rank of the resulting matrix.
*/
public static int solve(final Matrix matrix) {
return solve(matrix, DEFAULT_EPSILON);
}

/**
* Returns <code>true</code> if it is certain that the system of linear
* equations represented by the input matrix has no solutions. If there is
* a chance of feasibility, returns <code>false</code>. Uses the default
* epsilon.
*
* @param matrix  the matrix to check.
* @return <code>true</code> if there is no solution of the system
*         represented by the matrix and otherwise <code>false</code> is
*         returned.
*/
public static boolean isNotFeasible(final Matrix matrix) {
return isNotFeasible(matrix, DEFAULT_EPSILON);
}

/**
* Returns <code>true</code> if it is certain that the system of linear
* equations represented by the input matrix has no solutions. If there is
* a chance of feasibility, returns <code>false</code>.
*
* @param matrix  the matrix to check.
* @param epsilon the comparison epsilon.
* @return <code>true</code> if there is no solution of the system
*         represented by the matrix and otherwise <code>false</code> is
*         returned.
*/
public static boolean isNotFeasible(final Matrix matrix,
final double epsilon) {
checkNotNaN(epsilon, "The input epsilon is NaN.");
checkNotInfinite(epsilon, "The input epsilon is infinite: " + epsilon);
checkNotNegative(epsilon, "The input epsilon is negative: " + epsilon);

outer:
for (int r = 0; r < matrix.getHeight(); ++r) {
for (int c = 0; c < matrix.getWidth() - 1; ++c) {
if (!epsilonEquals(0.0, matrix.get(c, r), epsilon)) {
continue outer;
}
}

if (!epsilonEquals(0.0,
matrix.get(matrix.getWidth() - 1, r),
epsilon)) {
return false;
}
}

return true;
}

/**
* Constructs this eliminator.
*
* @param m       the matrix to eliminate.
* @param epsilon the epsilon value for comparisons.
*/
private GaussJordanElimination(final double[][] m, final double epsilon) {
checkNotNull(m, "The input matrix is null.");
checkNotNaN(epsilon, "The input epsilon is NaN.");
checkNotInfinite(epsilon, "The input epsilon is infinite: " + epsilon);
checkNotNegative(epsilon, "The input epsilon is negative: " + epsilon);

this.m = m;
this.epsilon = epsilon;
}

/**
* Performs the actual elimination.
*
* @return the rank of the resulting matrix.
*/
private int eliminate() {
int rowsProcessed = 0;

for (int k = 0; k != m[0].length; ++k) {
int ur = findUpmostRowWithPivotAtColumn(k, rowsProcessed);

if (ur == ROW_NOT_FOUND) {
continue;
}

swapRows(ur, rowsProcessed);
scaleRow(rowsProcessed, 1.0 / m[rowsProcessed][k]);

for (int r = 0; r != m.length; ++r) {
if (r != rowsProcessed) {
r,
rowsProcessed,
-m[r][k] / m[rowsProcessed][k]);
}
}

++rowsProcessed;
}

return rowsProcessed;
}

/**
* Returns <code>true</code> if <code>a</code> and <code>b</code> are within
* <code>epsilon</code> from each other.
*
* @param a       the first value.
* @param b       the second value.
* @param epsilon the maximum allowed distance.
* @return        <code>true</code> if <code>a</code> and <code>b</code> are
*                within <code>epsilon</code> from each other.
*/
public static boolean epsilonEquals(final double a,
final double b,
final double epsilon) {
return Math.abs(a - b) <= epsilon;
}

/**
* Checks the multiplication factor.
*
* @param factor the factor value to check.
* @throws IllegalArgumentException if the factor is <code>NaN</code> or is
*                                  infinite.
*/
private static void checkFactor(final double factor) {
checkNotNaN(factor, "The factor is NaN.");
checkNotInfinite(factor, "The factor is infinite: " + factor);
}

/**
* Implements an elementary matrix operation of adding a multiple of one row
* to another.
*
* @param targetRowIndex the index of the row to which to add.
* @param sourceRowIndex the index of the row which is added.
* @param factor         the factor by which to multiply each entry of the
*                       source row.
*/
final int sourceRowIndex,
final double factor) {
checkFactor(factor);
for (int i = 0; i != m[0].length; ++i) {
m[targetRowIndex][i] += m[sourceRowIndex][i] * factor;
}
}

/**
* Swaps to rows with given indices.
*
* @param rowIndex1 the index of a row.
* @param rowIndex2 the index of another row.
*/
private void swapRows(final int rowIndex1, final int rowIndex2) {
final double[] tmp = m[rowIndex1];
m[rowIndex1] = m[rowIndex2];
m[rowIndex2] = tmp;
}

/**
* Skips the first <code>skipRows</code> rows in the matrix and returns
* the index of a row containing non-zero value at column
* <code>columnIndex</code>.
*
* @param columnIndex the index of the target column.
* @param skipRows    the amount of uppermost rows to skip.
* @return            a row index.
*/
private int findUpmostRowWithPivotAtColumn(final int columnIndex,
final int skipRows) {
for (int i = skipRows; i < m.length; ++i) {
if (!epsilonEquals(m[i][columnIndex], 0.0, epsilon)) {
return i;
}
}

return ROW_NOT_FOUND;
}

/**
* Multiplies each entry of the specified matrix row by a given factor.
*
* @param rowIndex the index of the row.
* @param factor   the multiplication factor.
*/
private void scaleRow(final int rowIndex, final double factor) {
checkFactor(factor);
final double[] row = m[rowIndex];
for (int i = 0; i != row.length; ++i) {
row[i] *= factor;
}
}
}


Matrix.java:

package net.coderodde.math.linear;

/**
* This class implements a matrix of <code>double</code> entries.
*/
public class Matrix implements Cloneable {

/**
* The minimum allowed width of a matrix.
*/
private static final int MINIMUM_WIDTH = 1;

/**
* The minimum allowed height of a matrix.
*/
private static final int MINIMUM_HEIGHT = 1;

/**
* The actual storage of entries. This field is declared package private as
* to speed up the actual matrix operations.
*/
final double[][] m;

/**
* Constructs a new matrix with width <code>width</code> and height
* <code>height</code>.
*
* @param width  the width of the matrix.
* @param height the height of the matrix.
*/
public Matrix(final int width, final int height) {
checkWidth(width);
checkHeight(height);
m = new double[height][width];
}

/**
* Constructs a new matrix using the specified entries.
*
* @param data the data matrix containing the entries.
*/
public Matrix(final double[][] data) {
int h = data.length;
int w = 0;

for (final double[] row : data) {
w = Math.max(w, row.length);
}

m = new double[h][w];

for (int r = 0; r != data.length; ++r) {
for (int c = 0; c != data[r].length; ++c) {
m[r][c] = data[r][c];
}
}
}

/**
* Returns the height of this matrix.
*
* @return the height.
*/
public int getHeight() {
return m.length;
}

/**
* Returns the width of this matrix.
*
* @return the width.
*/
public int getWidth() {
return m[0].length;
}

/**
* Returns the entry at row <code>y</code> column <code>x</code>. (Both
* indices start at zero.)
*
* @param x the column index of the entry.
* @param y the row index of the entry.
* @return a matrix entry.
*/
public double get(final int x, final int y) {
checkColumnIndex(x);
checkRowIndex(y);
return m[y][x];
}

/**
* Sets the value for the entry at row <code>y</code> column <code>x</code>.
* (Both indices start at zero.)
*
* @param x     the column index.
* @param y     the row index.
* @param value the new value to set.
* @return      the old value.
*/
public double set(final int x, final int y, final double value) {
checkColumnIndex(x);
checkRowIndex(y);
final double old = m[y][x];
m[y][x] = value;
return old;
}

/**
* Returns another matrix with exactly same contents as this matrix.
*
* @return the clone matrix.
*/
@Override
public Matrix clone() {
final Matrix clone = new Matrix(getWidth(), getHeight());

for (int row = 0; row < getHeight(); ++row) {
for (int column = 0; column < getWidth(); ++column) {
clone.set(column, row, get(column, row));
}
}

return clone;
}

@Override
public String toString() {
final StringBuilder sb = new StringBuilder();
final String formatString = "%+f ";

for (int r = 0; r < getHeight(); ++r) {
for (int c = 0; c < getWidth(); ++c) {
sb.append(String.format(formatString, get(c, r)));
}

sb.append('\n');
}

return sb.toString();
}

/**
* Checks the width.
*
* @param width the width to check.
* @throws IllegalArgumentException if the width is too small.
*/
private void checkWidth(final int width) {
if (width < MINIMUM_WIDTH) {
throw new IllegalArgumentException(
"The matrix width is too small. " +
"Requested width: " + width + ", " +
"mimimum allowed: " + MINIMUM_WIDTH);
}
}

/**
* Checks the height.
*
* @param height the height to check.
* @throws IllegalArgumentException if the height is too small.
*/
private void checkHeight(final int height) {
if (height < MINIMUM_HEIGHT) {
throw new IllegalArgumentException(
"The matrix width is too small. " +
"Requested width: " + height + ", " +
"mimimum allowed: " + MINIMUM_HEIGHT);
}
}

/**
* Checks that the given row index is valid.
*
* @param rowIndex the index of a row to check.
* @throws IllegalArgumenException if the index is out of bounds.
*/
private void checkRowIndex(final int rowIndex) {
if (rowIndex < 0) {
throw new IllegalArgumentException(
"Row index is negative: " + rowIndex);
}

if (rowIndex >= m.length) {
throw new IllegalArgumentException(
"Row index is too large. " +
"Received: " + rowIndex + ", the height of the matrix: " +
m.length);
}
}

/**
* Checks that the given column index is valid.
*
* @param columnIndex the index of a column to check.
* @throws IllegalArgumentException if the index is out of bounds.
*/
private void checkColumnIndex(final int columnIndex) {
if (columnIndex < 0) {
throw new IllegalArgumentException(
"Column index is negative: " + columnIndex);
}

if (columnIndex >= m[0].length) {
throw new IllegalArgumentException(
"Column index is too large. " +
"Received: " + columnIndex + ", the width of the matrix: " +
m[0].length);
}
}
}


Utils.java:

package net.coderodde.math.linear;

/**
* This class defines some common utility methods.
*/
public class Utils {

/**
* Checks that the input number is not infinite and if it is, throws
* an exception with the specified message.
*
* @param value  the value to check.
* @param errmsg the message to pass to the exception upon failure.
*/
public static void checkNotInfinite(final double value,
final String errmsg) {
if (Double.isInfinite(value)) {
throw new IllegalArgumentException(errmsg);
}
}

/**
* Checks that the input number is not <code>NaN</code> and if it is,
* throws an exception with the specified message.
*
* @param value  the value to check.
* @param errmsg the message to pass to the exception upon failure.
*/
public static void checkNotNaN(final double value, final String errmsg) {
if (Double.isNaN(value)) {
throw new IllegalArgumentException("The value is NaN.");
}
}

/**
* Checks that the input number is not negative and if it is, throws an
* exception with the specified message.
*
* @param value  the value to check.
* @param errmsg the message to pass to the exception upon failure.
*/
public static void checkNotNegative(final double value,
final String errmsg) {
if (value < 0.0) {
throw new IllegalArgumentException(errmsg);
}
}

/**
* Checks that the input reference is not <code>null</code> and if it is,
* throw an exception with the supplied error message.
*
* @param o      the reference to check.
* @param errmsg the error message to pass to the exception upon failure.
*/
public static void checkNotNull(final Object o, final String errmsg) {
if (o == null) {
throw new IllegalArgumentException(errmsg);
}
}
}


Demo.java:

package net.coderodde.math.linear;

import java.util.Random;
import static net.coderodde.math.linear.GaussJordanElimination.isNotFeasible;

/**
* This class implements a demonstration.
*/
public class Demo {

private static final String GAY_BAR;

static {
final StringBuilder sb = new StringBuilder(80);

for (int i = 0; i < 80; ++i) {
sb.append('-');
}

GAY_BAR = sb.toString();
}

public static void main(final String... args) {
helloWorldDemo();
bar();
laaargggeeeDemmoo();
}

private static void helloWorldDemo() {
Matrix m = new Matrix(new double[][] {
{ 1.0, 3.0, -2.0, 5.0 },
{ 3.0, 5.0, 6.0, 7.0  },
{ 2.0, 4.0, 3.0, 8.0  },
});

System.out.println(m);

int rank = GaussJordanElimination.solve(m);

System.out.println(m);
System.out.println("Rank: " + rank);
System.out.println("Feasible: " + isNotFeasible(m));

bar();

m = new Matrix(new double[][] {
{ 1.0, 3.0, -2.0, 5.0 },
{ 3.0, 5.0, 6.0, 7.0  },
{ 4.0, 8.0, 6.0, 16.0 },
{ 2.0, 4.0, 3.0, 8.0  },
{ 1.0, 1.0, 1.0, -5.0 },
});

System.out.println(m);

rank = GaussJordanElimination.solve(m);

System.out.println(m);
System.out.println("Rank: " + rank);
System.out.println("Feasible: " + isNotFeasible(m));

bar();

m = new Matrix(new double[][] {
{ 1.0, 3.0, -2.0, 5.0 },
{ 3.0, 5.0, 6.0, 7.0  },
{ 3.0, 5.0, 6.0, 8.0  },
});

System.out.println(m);

rank = GaussJordanElimination.solve(m);

System.out.println(m);
System.out.println("Rank: " + rank);
System.out.println("Feasible: " + isNotFeasible(m));
}

private static void bar() {
System.out.println(GAY_BAR);
}

private static void laaargggeeeDemmoo() {
final long seed = System.currentTimeMillis();
final Random rnd = new Random(seed);
final Matrix m = new Matrix(1000, 500);

System.out.println("Seed: " + seed);

for (int r = 0; r < m.getHeight(); ++r) {
for (int c = 0; c < m.getWidth(); ++c) {
m.set(c, r, rnd.nextInt(101) - 50);
}
}

long ta = System.currentTimeMillis();
int rank = GaussJordanElimination.solve(m);
long tb = System.currentTimeMillis();

System.out.println("Rank: " + rank + ", time: " + (tb - ta) + " ms.");
System.out.println("Feasible: " + isNotFeasible(m));
}
}


GaussJordanElimination.java

/**
* Caches the actual matrix.
*/
private final double[][] m;


You could use more descriptive name that m maybe something like content which can tell me what is m without to read the comment.

public static int solve(final Matrix matrix, final double epsilon) {
return new GaussJordanElimination(matrix.m, epsilon).eliminate();
}


If you really need matrix.m as argument why you pass the whole matrix object ?

if (!epsilonEquals(0.0, matrix.get(c, r), epsilon)) {
continue outer;
}


There is 0.0 as magic number but what is its purpose - this can be some variable with proper name.

Also you alternate public and private methods - it would be better if you group them let say first public and below private methods.

  public static boolean epsilonEquals(final double a,
final double b,
final double epsilon) {
return Math.abs(a - b) <= epsilon;
}


epsilonEquals() is not appropriate for boolean methods - maybe something like isInEpsilonRange() (just as example) would be more descriptive.

private void swapRows(final int rowIndex1, final int rowIndex2)


Instead rowIndex* you could use first(second)RowIndex or something similar.

Matrix.java

public double get(final int x, final int y)


You could use columnIndex and rowIndex instead x and y.

Utils.java

Maybe should be named to something like Validator with validateX() methods. All of this methods (for now) perform some validation on input data.