Sparse matrix library for Java

Question

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 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)")
• The SparseDoubleMatrix2D class of the Colt library throws a Java heap space error.
• The DMatrixSparseCSC class of the Efficient Java Matrix Library throws a java.lang.NegativeArraySizeException when initializing a large matrix. This has been fixed since the question -- see the author's comment and the accepted answer.
• 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. Neither FlexCompColMatrix, nor FlexCompRowMatrix finish in 10 minutes. CompRowMatrix and CompColMatrix 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:

1. support the definition of semirings other than the conventional plus-times arithmetic one (e.g. lor-land, min-plus)
2. support masking operations (only perform a given operation for elements selected by a mask)
3. 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.

Answer 1

There are two libraries I can recommend. Both support sparse matrices, including matrix-matrix multiplication, matrix-matrix element-wise multiplication and matrix-vector multiplication. Both are open-source, actively maintained, and available from the Maven Central.

1. EJML (Efficient Java Matrix Library) is Apache-licensed (ASLv2) - [source code], [Maven]. Recently (Sep 2020) it has been extended with support for semirings.

2. ojAlgo ("oj! Algorithms") is MIT-licensed - [source code], [Maven].

For the sparse workloads I tested, EJML had far superior performance, so it's worth trying that one first.