1
\$\begingroup\$

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) {
                    addToRowMultipleOfAnotherRow(
                            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.
     */
    private void addToRowMultipleOfAnotherRow(final int targetRowIndex,
                                              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));
    }
}
\$\endgroup\$
2
\$\begingroup\$

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.

I hope that this will help you :)

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.