Add innerProduct for sparse vectors. - Githubissues

lessthanoptimal / ejml

A fast and easy to use linear algebra library written in Java for dense, sparse, real, and complex matrices.

https://ejml.org

565 stars 117 forks source link

Add innerProduct for sparse vectors. #181

Closed spensonshih closed 1 year ago

spensonshih commented 1 year ago

PR for #180

The new version of innerProduct will be specialised to take in sparse vectors for A and C, and a matrix B.

scalar = A^T^ B C

By looping through only non-zero elements of the vectors, avoids a lot of unnecessary operations and have a significant performance improvement when used with sparse vectors.

And innerProductSelfSymmetrical, specialised to take in sparse vector A, and a positive semi-definite covariance matrix B.

scalar = A^T B A

Further enhances the innerProduct, utilising the matrix symmetry, it will calculate the product using just the lower (or upper) triangle, multiply this by 2, then add to the product of the matrix diagonal.

Before submitting this PR, please make sure:

[X] Your code is covered by tests
[X] You ran ./gradlew spotlessJavaApply

lessthanoptimal commented 1 year ago

thanks for the PR. Will probably end up shuffling around its location the another class, but that can be done later on.

A good unit test would be to compare it compare it against two equivalent multiplications.
A JMH benchmark. There's room for a few optimizations, but it would be interesting to have this implementation as a baseline. Plus a JMH benchmark will be created anyways for regression testing.

Inside of main/ejml-dsparse/src/org/ejml/sparse/csc/mult there are several examples for JMH and you could put it in a new class there.

I think adding a concurrent implementation should be straight forward. That can be done in another PR.

lessthanoptimal commented 1 year ago

Ignore comment about unit tests. I missed the ones you added.

spensonshih commented 1 year ago

Thanks for the prompt feedback @lessthanoptimal. I've added the JMH benchmarks.

lessthanoptimal commented 1 year ago

almost there

lessthanoptimal commented 1 year ago

Can you squash it into a single commit? When I have a break from this conference I'll do a local checkout then hopefully approve it. As a warning, after this gets merged I'm going to create a PR which does some refactoring. Mostly move the location of files. It would take longer to explain where everything should go than to do it.

spensonshih commented 1 year ago

@lessthanoptimal Apologies for the delay, I had some hardware troubles yesterday. I've now squashed into a single commit.

lessthanoptimal commented 1 year ago

looks like a spotless issue snuck in. ./gradlew :main:spotlessApply squash again, then I'll merge it.

spensonshih commented 1 year ago

Fixed the spotless issue and squashed.