I am looking for a sparse matrix library in Java that can do multiplications on sparse integer matrices, where the matrices represent the adjacency relations of a graph. The requirement is roughly the following: the library should be able to load and multiply a few matrices of 10M×10M elements, containing approx. 5M non-zero elements each, when running on a commodity machine (~16 GBs of RAM). The Eigen library for C++ satisfies this requirement. However, I couldn't find a good alternative for Java.
I looked at the following libraries:
SparseMatrixclass in the Spark ML library only seems to support multiplication with a dense matrix.
OpenMapRealMatrixclass of Apache Commons Math throws a
NumberIsTooLargeException, as it only supports matrices with 2B elements ("40,000,000,000 is larger than, or equal to, the maximum (2,147,483,647)")
SparseDoubleMatrix2Dclass of the Colt library throws a Java heap space error.
DMatrixSparseCSCclass of the Efficient Java Matrix Library
throws aThis has been fixed since the question -- see the author's comment and the accepted answer.
java.lang.NegativeArraySizeExceptionwhen initializing a large matrix.
LinkedSparseMatrixclass of Matrix Toolkit Java is very quick to initialize, but does not handle multiplication well - multiplying an empty 1M×1M matrix takes ~6 minutes.
CompDiagMatrixruns out of memory for a matrix of this size. Neither
FlexCompRowMatrixfinish in 10 minutes.
CompColMatrixhave good performance for ~20k×20k matrices, but break down in performance for larger ones. (The Javadoc for the latest stable version, 1.0.4 does not advise which sparse matrix to use for static cases. A pull request submitted more detailed documentation since, but 1.0.5-SNAPSHOT never made it to release and the project is now archived.)
- Graphulo is an implementation of GraphBLAS, but is very complicated to use as it is designed to run on top of the Apache Accumulo database.
- The Universal Java Matrix Package (UJMP) is a good fit on paper, but does not provide very good performance. Also, it seems abandoned and it is LGPL-licensed.
- Finally, various JCuda libraries could be useful, including JCusparse and JNvgraph, but all of these require a GPU.
I have also found a comprehensive survey at https://java-matrix.org/, created by the author of UJMP, which shows the state of the art in ~2015 and highlights that very few libraries support sparse matrices.
A related question for a C/C++ library from 2010: Looking for a C/C++ interface for efficient computation of huge sparse matrix in Linux
Update (late 2019): I've now researched this area for over a year and identified a few requirements that sparse matrix libraries need to meet in order to express graph algorithms and perform them efficiently:
- support the definition of semirings other than the conventional plus-times arithmetic one (e.g. lor-land, min-plus)
- support masking operations (only perform a given operation for elements selected by a mask)
- allow multi-threaded execution
As of now, I could not find a Java library that satisfies any of the requirements above. Therefore, I have switched to C and use SuiteSparse:GraphBLAS.
Update (Sep 2020): EJML now satisfies requirement #1, see the pull request introducing support for semirings.