CODEWITHSUNDEEP
c++sparse-matrixeigen
Jay
Jay

Reputation: 359

Performance bottleneck in Eigen program

As a part of a larger problem, I'm running into a performance bottle neck when dealing with Sparse Matrices in Eigen.

I need to subtract a floating point number (x) from each element in a Sparse Matrix (G), including the positions where the coefficients are zero. So the zero elements should have a value -x

The way I do this at the moment is as follows:

//calculate G
x=0.01;
for(int i=0;i<rows;i++){
   for (int j=0; j<cols; j++) {
       G.coeffRef(i, j) -= x;
   }
}

When the size of G is large, this simple calculation is a bottleneck.

I've also tried to convert sparse matrix G into a dense one and subtracting P(a matrix filled with values x):

MatrixXd DenseG=MatrixXd(G);
x=0.01;
for(int i=0;i<rows;i++){
   for (int j=0; j<cols; j++) {
       DenseG(i, j) -= x;
   }
}

This method is so much faster. However, I'm just wondering if there are other workarounds that does not involve converting G into a dense one, which require a lot of memory in the case of very large matrices.

Upvotes: 0

Views: 346

Answers (2)

ggael
ggael

Reputation: 29205

As Avi Ginsburg said, this operation results in a dense matrix loosing all the structure of G-X where G is the initial sparse matrix and X is an abstract dense matrix filled with x.

I would recommend you to try to keep these two terms separated in the rest of your algorithm and update the math to exploit this special structure. For instance, if the next step is to multiply it to a dense vector v, then you can advantageously exploit that:

(G-X)*v == (G*v).array()-v.sum()*x

Upvotes: 1

Avi Ginsburg
Avi Ginsburg

Reputation: 10596

Your "sparse" calculation is effectively a dense one as you're subtracting from all n^2 elements. A major difference is that instead of having a single operation done on a swath of memory, you have to allocate memory for the matrix pretty much every time you access a zero element. In general, sparse matrices are efficient when they are sparse, and incur a lot of overhead for most operations. That overhead is balanced out by only having to store very few elements, and therefore, only repeat the operations a few times.

Another possible option is to take advantage of Eigen's lazy evaluation, but that kinda depends on your exact requirements, which you have not listed here.

Upvotes: 3

Related Questions