How to perform quick element-wise multiplication with sparse matrices

I am working with sparse integer matrices to perform graph analytics with my Master's student @missvarhegyi.

We have been trying to find a Java library supporting quick matrix-matrix (MM) and element-wise matrix multiplication operations for a while now. So far, EJML seems to the closest fit to our needs: it provides very good performance for MM multiplications. However, we could not get element-wise multiplication run as quickly as it should (based on the fact that its computational complexity of slower than MM multiplications).

    @Test
    public void test() {
        int n = 100_000;

        DMatrixSparseTriplet triplets = new DMatrixSparseTriplet(n, n, n);
        for (int i = 0; i < n; i++) {
            triplets.addItem(i, i, 1);
        }

        DMatrixSparseCSC M = ConvertDMatrixStruct.convert(triplets, (DMatrixSparseCSC) null);
        DMatrixSparseCSC MM = new DMatrixSparseCSC(n, n, 0);
        DMatrixSparseCSC EW = new DMatrixSparseCSC(n, n, 0);

        long t1 = System.currentTimeMillis();
        ImplSparseSparseMult_DSCC.mult(M, M, MM, null, null);
        long t2 = System.currentTimeMillis();
        CommonOps_DSCC.elementMult(M, M, EW, null, null);
        long t3 = System.currentTimeMillis();

        System.out.println("MM: " + (t2 - t1));
        System.out.println("EW: " + (t3 - t1));
    }

This shows that the element-wise multiplication is significantly slower.

MM: 20
EW: 9848

For larger n values, the difference gets larger.

We also tried the ejml-simple library and performed the multiplication as follows:

        SimpleOperations_SPARSE ops = new SimpleOperations_SPARSE();
        ops.elementMult(M, M, EW);

However, this was similarly slow.

MM: 20
EW: 9141

How can we perform quick element-wise multiplications?

For sparse matrices, element-wise multiplication is non trivial. If the non-zero pattern doesn't match it needs to modify the array, grow, and re-organize it. If you run it again with the same matrix it should be much faster.

Results below for running it twice on the same matrix:

MM: 13 EW: 5683 EW: 4

Now, I do suspect that something inefficient is going on the first time. I'll look into it.

@Test public void test() { int n = 100_000;

DMatrixSparseTriplet triplets = new DMatrixSparseTriplet(n, n, n);
for (int i = 0; i < n; i++) {
    triplets.addItem(i, i, 1);
}

DMatrixSparseCSC M = ConvertDMatrixStruct.convert(triplets,

(DMatrixSparseCSC) null); DMatrixSparseCSC MM = new DMatrixSparseCSC(n, n, 0); DMatrixSparseCSC EW = new DMatrixSparseCSC(n, n, 0);

long t1 = System.currentTimeMillis();
ImplSparseSparseMult_DSCC.mult(M, M, MM, null, null);
long t2 = System.currentTimeMillis();
CommonOps_DSCC.elementMult(M, M, EW, null, null);
long t3 = System.currentTimeMillis();
CommonOps_DSCC.elementMult(M, M, EW, null, null);
long t4 = System.currentTimeMillis();

System.out.println("MM: " + (t2 - t1));
System.out.println("EW: " + (t3 - t2));
System.out.println("EW: " + (t4 - t3));

}

On Fri, Oct 19, 2018 at 6:23 AM Gabor Szarnyas notifications@github.com wrote:

I am working with sparse integer matrices to perform graph analytics with my Master's student @missvarhegyi https://github.com/missvarhegyi.

We have been trying to find a Java library supporting quick matrix-matrix (MM) and element-wise matrix multiplication operations for a while now https://softwarerecs.stackexchange.com/questions/51330/sparse-matrix-library-for-java. So far, EJML seems to the closest fit to our needs: it provides very good performance for MM multiplications. However, we could not get element-wise multiplication run as quickly as it should (based on the fact that its computational complexity of slower than MM multiplications).
@Test
public void test() {
    int n = 100_000;

    DMatrixSparseTriplet triplets = new DMatrixSparseTriplet(n, n, n);
    for (int i = 0; i < n; i++) {
        triplets.addItem(i, i, 1);
    }

    DMatrixSparseCSC M = ConvertDMatrixStruct.convert(triplets, (DMatrixSparseCSC) null);
    DMatrixSparseCSC MM = new DMatrixSparseCSC(n, n, 0);
    DMatrixSparseCSC EW = new DMatrixSparseCSC(n, n, 0);

    long t1 = System.currentTimeMillis();
    ImplSparseSparseMult_DSCC.mult(M, M, MM, null, null);
    long t2 = System.currentTimeMillis();
    CommonOps_DSCC.elementMult(M, M, EW, null, null);
    long t3 = System.currentTimeMillis();

    System.out.println("MM: " + (t2 - t1));
    System.out.println("EW: " + (t3 - t1));
}
This shows that the element-wise multiplication is significantly slower.

MM: 20EW: 9848

For larger n values, the difference gets larger.

We also tried the ejml-simple library and performed the multiplication as follows:
    SimpleOperations_SPARSE ops = new SimpleOperations_SPARSE();
    ops.elementMult(M, M, EW);
However, this was similarly slow.

MM: 20EW: 9141

How can we perform quick element-wise multiplications?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/lessthanoptimal/ejml/issues/48, or mute the thread https://github.com/notifications/unsubscribe-auth/AAtHVwuRA3goA3MLABtUP5zcXGkFV7CNks5umdJUgaJpZM4XwWap .

-- "Now, now my good man, this is no time for making enemies." — Voltaire (1694-1778), on his deathbed in response to a priest asking that he renounce Satan.

Well that was easy to fix:

MM: 12 EW: 12 EW: 4

Checkout and build the latest SNAPSHOT or add this to your code

C.growMaxLength(Math.min(A.nz_length,B.nz_length),false);

On Fri, Oct 19, 2018 at 7:10 AM Peter A peter.abeles@gmail.com wrote:

For sparse matrices, element-wise multiplication is non trivial. If the non-zero pattern doesn't match it needs to modify the array, grow, and re-organize it. If you run it again with the same matrix it should be much faster.

Results below for running it twice on the same matrix:

MM: 13 EW: 5683 EW: 4

Now, I do suspect that something inefficient is going on the first time. I'll look into it.

@Test public void test() { int n = 100_000;
DMatrixSparseTriplet triplets = new DMatrixSparseTriplet(n, n, n);
for (int i = 0; i < n; i++) {
    triplets.addItem(i, i, 1);
}

DMatrixSparseCSC M = ConvertDMatrixStruct.convert(triplets, (DMatrixSparseCSC) null);
DMatrixSparseCSC MM = new DMatrixSparseCSC(n, n, 0);
DMatrixSparseCSC EW = new DMatrixSparseCSC(n, n, 0);

long t1 = System.currentTimeMillis();
ImplSparseSparseMult_DSCC.mult(M, M, MM, null, null);
long t2 = System.currentTimeMillis();
CommonOps_DSCC.elementMult(M, M, EW, null, null);
long t3 = System.currentTimeMillis();
CommonOps_DSCC.elementMult(M, M, EW, null, null);
long t4 = System.currentTimeMillis();

System.out.println("MM: " + (t2 - t1));
System.out.println("EW: " + (t3 - t2));
System.out.println("EW: " + (t4 - t3));
}

On Fri, Oct 19, 2018 at 6:23 AM Gabor Szarnyas notifications@github.com wrote:
I am working with sparse integer matrices to perform graph analytics with my Master's student @missvarhegyi https://github.com/missvarhegyi.

We have been trying to find a Java library supporting quick matrix-matrix (MM) and element-wise matrix multiplication operations for a while now https://softwarerecs.stackexchange.com/questions/51330/sparse-matrix-library-for-java. So far, EJML seems to the closest fit to our needs: it provides very good performance for MM multiplications. However, we could not get element-wise multiplication run as quickly as it should (based on the fact that its computational complexity of slower than MM multiplications).
@Test
public void test() {
    int n = 100_000;

    DMatrixSparseTriplet triplets = new DMatrixSparseTriplet(n, n, n);
    for (int i = 0; i < n; i++) {
        triplets.addItem(i, i, 1);
    }

    DMatrixSparseCSC M = ConvertDMatrixStruct.convert(triplets, (DMatrixSparseCSC) null);
    DMatrixSparseCSC MM = new DMatrixSparseCSC(n, n, 0);
    DMatrixSparseCSC EW = new DMatrixSparseCSC(n, n, 0);

    long t1 = System.currentTimeMillis();
    ImplSparseSparseMult_DSCC.mult(M, M, MM, null, null);
    long t2 = System.currentTimeMillis();
    CommonOps_DSCC.elementMult(M, M, EW, null, null);
    long t3 = System.currentTimeMillis();

    System.out.println("MM: " + (t2 - t1));
    System.out.println("EW: " + (t3 - t1));
}
This shows that the element-wise multiplication is significantly slower.

MM: 20EW: 9848

For larger n values, the difference gets larger.

We also tried the ejml-simple library and performed the multiplication as follows:
    SimpleOperations_SPARSE ops = new SimpleOperations_SPARSE();
    ops.elementMult(M, M, EW);
However, this was similarly slow.

MM: 20EW: 9141

How can we perform quick element-wise multiplications?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/lessthanoptimal/ejml/issues/48, or mute the thread https://github.com/notifications/unsubscribe-auth/AAtHVwuRA3goA3MLABtUP5zcXGkFV7CNks5umdJUgaJpZM4XwWap .
-- "Now, now my good man, this is no time for making enemies." — Voltaire (1694-1778), on his deathbed in response to a priest asking that he renounce Satan.

-- "Now, now my good man, this is no time for making enemies." — Voltaire (1694-1778), on his deathbed in response to a priest asking that he renounce Satan.

Thanks for the quick response and fixing the issue promptly.

If you profile EJML and compare it against other libraries could you post the results? I've not done that yet and would be interested seeing how it compares.

Sure, I'll share the results next week. We have a quite peculiar workload: counting triangles for each vertex in a graph, with the heavy lifting delegated to MM and element-wise matrix multiplications on adjacency matrices. We expected this to be an easy problem, but it turned out to be difficult enough to stress most Java sparse matrix libraries.

lessthanoptimal / ejml

How to perform quick element-wise multiplication with sparse matrices #48