Java Vector inner products

Question

I have an arraylist of m-dimensional vectors (stored as simple arrays) v1, v2 ... vn.

I have to repeatedly calculate inner products between two vectors that I select from among these vectors.

One way to do this is a simple for loop across all it's components.

double sum=0;
for(int i=0; i<m; i++)
    sum+=v1[i]*v2[i];

This is pretty much the only linear algebra operation I intend on performing on my data.

1. Would it be more efficient to import a linalg library like JAMA or la4j, store everything as matrices, and calculate the inner products? (these aren't even large matrix multiplications, just inner products between 1D vectors)

2. How does la4j(etc) implement a dot product? Would it not also iterate through each index and multiply each pair of components?

Answer 1

la4j is Open Source, have a look at the code. Using the AbstractVector's inner product is less efficient than your own code, since it instantiates additional operation objects, here the OoPlaceInnerProduct.

However: In most cases I would still prefer using an existing, well-tested vector math package than implementing my own one. (Knuth: “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil”.)

Note that multithreading doesn't help either. Even the highly efficient LAPACK package uses the same code as yours.

Answer 2

If you want to compute all inner products i reccomend this: in matrix A store your vectors in rows, and in B, store them in cols. Then in A*B you will havat position (i,j) inner product of v_i and v_j.

The trick is that normal matrix multiplication takes n^3 time, but some clever algorithm have more efficient methods, but only for ~ 30 and more vectors.

Answer 3

Regaring the la4j libray: an upcomming version 0.5.0 uses lightweight sparse iteratos so you should not worry about iterating through zero values in sparse vectors. Here is the API example

Vector a = new BasicVector(...); // dense
Vector b = new CompressedVector(...); // sparse
double dot = a.innerProduct(b);

You can combine any possible pair: sparse-dense, sparse-sparse, dense-dense, dense-sparse. The la4j library will always be using the most efficient algorithm depending on your data.