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:
- The
SparseMatrix
class in the Spark ML library only seems to support multiplication with a dense matrix.- Digging a bit deeper, the Breeze library used by Spark ML states the following: "CSCMatrices are not fully supported yet. They are missing several basic operations."
- It's also worth noting that internally, Breeze uses the
netlib-java
library.
- The
OpenMapRealMatrix
class of Apache Commons Math throws aNumberIsTooLargeException
, as it only supports matrices with 2B elements ("40,000,000,000 is larger than, or equal to, the maximum (2,147,483,647)") - The
SparseDoubleMatrix2D
class of the Colt library throws a Java heap space error. - The
DMatrixSparseCSC
class of the Efficient Java Matrix Librarythrows aThis has been fixed since the question -- see the author's comment and the accepted answer.java.lang.NegativeArraySizeException
when initializing a large matrix. - The
LinkedSparseMatrix
class of Matrix Toolkit Java is very quick to initialize, but does not handle multiplication well - multiplying an empty 1M×1M matrix takes ~6 minutes.CompDiagMatrix
runs out of memory for a matrix of this size. NeitherFlexCompColMatrix
, norFlexCompRowMatrix
finish in 10 minutes.CompRowMatrix
andCompColMatrix
have 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.
See also the GitHub issue on the performance of sparse matrix multiplication in MTJ.
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.
Update (Feb 2021): EJML v0.40 supports all requirements, offering some degree of concurrency and masks.