Representing a 100K X 100K matrix in Java

Question

How can I store a 100K X 100K matrix in Java?

I can't do that with a normal array declaration as it is throwing a java.lang.OutofMemoryError.

Answer 1

The Colt library has a sparse matrix implementation for Java.

You could alternatively use Berkeley DB as your storage engine.

Now if your machine has enough actual RAM (at least 9 gigabytes free), you can increase the heap size in the Java command-line.

Answer 2

If the vast majority of entries in your matrix will be zero (or even some other constant value) a sparse matrix will be suitable. Otherwise it might be possible to rewrite your algorithm so that the whole matrix doesn't exist simultaneously. You could produce and consume one row at a time, for example.

Answer 3

Sounds like you need a sparse matrix. Others have already suggested good 3rd party implementations that may suite your needs...

Depending on your applications, you could get away without a third-party matrix library by just using a Map as a backing-store for your matrix data. Kind of...

public class SparseMatrix<T> {
    private T defaultValue;
    private int m;
    private int n;
    private Map<Integer, T> data = new TreeMap<Integer, T>();
    /// create a new matrix with m rows and n columns
    public SparseMatrix(int m, int n, T defaultValue) {
        this.m = m;
        this.n = n;
        this.defaultValue = defaultValue;
    }
    /// set value at [i,j] (row, col)
    public void setValueAt(int i, int j, T value) {
        if (i >= m || j >= n || i < 0 || j < 0) 
            throw new IllegalArgumentException(
                    "index (" + i + ", " +j +") out of bounds");        
        data.put(i * n + j, value);
    }
    /// retrieve value at [i,j] (row, col)
    public T getValueAt(int i, int j) {
        if (i >= m || j >= n || i < 0 || j < 0) 
            throw new IllegalArgumentException(
                    "index (" + i + ", " +j +") out of bounds");
        T value = data.get(i * n + j);
        return value != null ? value : defaultValue;
    }
}

A simple test-case illustrating the SparseMatrix' use would be:

public class SparseMatrixTest extends TestCase {
    public void testMatrix() {
        SparseMatrix<Float> matrix = 
            new SparseMatrix<Float>(100000, 100000, 0.0F);
        matrix.setValueAt(1000, 1001, 42.0F);
        assertTrue(matrix.getValueAt(1000,1001) == 42.0);
        assertTrue(matrix.getValueAt(1001,1000) == 0.0);        
    }   
}

This is not the most efficient way of doing it because every non-default entry in the matrix is stored as an Object. Depending on the number of actual values you are expecting, the simplicity of this approach might trump integrating a 3rd-party solution (and possibly dealing with its License - again, depending on your situation).

Adding matrix-operations like multiplication to the above SparseMatrix implementation should be straight-forward (and is left as an exercise for the reader ;-)