Sparse and Special Structure Matrices

ojAlgo’s MatrixStore interface largely defines what you can do with matrices. There are many implementations of that interface provided. They store the elements differently and exploit structure to perform operations more efficiently. If you have special requirements, implementing your own MatrixStore is very easy.

Custom MatrixStore Example

Here’s an example how to implement a simple eye matrix. From this it should be possible to deduce how to implement any other special structered matrix.

There are 2 implementations described in the example:

  1. MostBasicEye just implements the 4 methods that all MatrixStore implementations have to implement. As you can see these are trivial to implement, and this class is already fully functional.
  2. BetterPerformingEye extends MostBasicEye and adds a few methods that make it perform better. It’s just a handfull additional methods that in most cases would be trivial to implement but doing so can make a big difference.

To further improve things you may override any/all additional methods. This would be specific to your use case.

class CreateCustomMatrixStore
ojAlgo
2020-09-14


Compare multiplication
MostBasicEye multiplied in 6.852596385E9ns
Built-in ojAlgo multiplied in 8.480996E7ns
BetterPerformingEye multiplied in 5.2626592E7ns

Compare QR decomposition
MostBasicEye decomposed in 1.69935516E8ns
Built-in ojAlgo decomposed in 1.53854866E8ns
BetterPerformingEye decomposed in 2.1318605E7ns

Sparse Matrix Example

Among the provided MatrixStore implementations is a general purpose sparse matrix called SparseStore. Here’s a little example of what you can do with that, as well as a couple of the other special matrix types.

The example program below outputs various execution times, but the interesting part is not the speed. The main takeaway here is that the calculations are at all possible. If all the matrices created in the example had been dense implementations this program would require more than 1TB of memory to execute. Yet it runs with the default settings of a standard JVM (and finishes in a few seconds).

The execution times are significantly different for the various matrix multiplication alternatives in the example program. You’re encouraged to think about why/how that is, and then check the source code to verify your conclusions.

class SparseMatrices
ojAlgo
2020-09-14


Sparse-Sparse multiplication
100314 non-zeroes out of 10000000000 matrix elements calculated in 54.874324ms

Sparse-Identity multiplication
100000 non-zeroes out of 10000000000 matrix elements calculated in 27.532112ms

Sparse-Zero multiplication
0 non-zeroes out of 10000000000 matrix elements calculated in 14.865259ms

Identity-Sparse multiplication
100000 non-zeroes out of 10000000000 matrix elements calculated in 11.162651ms

Zero-Sparse multiplication
0 non-zeroes out of 10000000000 matrix elements calculated in 0.499874ms

Scale logical structure
200000 x 200000 matrix scaled in 30.004948ms

Leave a Reply