Hi,

I have a sparse symmetric matrix (60000 * 60000) to fill, each row/col has less than 5 non-zero entries, so VERY sparse..

I followed the tutorial
http://eigen.tuxfamily.org/dox-devel/Tu ... parse.html
and did something like this:

SparseMatrix<float> Lu(numVertices, numVertices);
Lu.reserve(numVertices*5);
for (int j=0; j<numVertices; j++){
Lu.startVec(j);
for (int i=0; i<numVertices; i++){
Lu.insertBack(i,j) = weight;
}
}
Lu.finalize();

However, it takes around 2 minutes to fill this matrix on my machine: Win7 64bit; MSVC 2008 Debug mode; Intel-i3 3.3GHz CPU; 8G RAM. That's way to slow.....

Debug mode is indeed very slow. Retry in Release mode. That should not take more than 1 sec.

Hmm, in the Debug mode, filling both A and B and solve(SimplicialCholesky) for x takes 136 seconds. While in Release mode, it still takes 22 seconds to fill and solve with SimplicialCholesky. And 20 seconds are spent on filling.

Is my way of filling the sparse matrix the fastest method?

ggael wrote:Debug mode is indeed very slow. Retry in Release mode. That should not take more than 1 sec.

Following http://eigen.tuxfamily.org/dox/TutorialSparse.html

I also tried the following syntax. However, it gives the same performance in terms of speed with the above method (using insertBack) which is supposed to be the fastest way to fill a Sparse matrix.

DynamicSparseMatrix<float> aux(1000,1000);
aux.reserve(estimated_number_of_non_zero); // optional
for (...)
for each j // the j can be random
for each i interacting with j // the i can be random
aux.coeffRef(i,j) += foo(i,j);

hm, that's weird because insertBack does roughly the same than std::vector::push_back. Are you sure that's not your code to compute the coefficients which is slow?

Ok, I will try debugging that part.

BTW, the size of the sparse matrix is determined only at run time. i.e.,

SparseMatrix<float> Lu(numVertices, numVertices); where numVertices can only be calculated at run time. Will this affect the filling speed?

ggael wrote:hm, that's weird because insertBack does roughly the same than std::vector::push_back. Are you sure that's not your code to compute the coefficients which is slow?

I tried the following simple code. On my laptop( Ubuntu 10.10; Release Mode in KDevelop; Intel Pentium 1.8G CPU; 2.5G RAM), it takes 7 seconds. Am I missing something? Since it really shouldn't be this slow. Maybe some compiling options that's are important?


By changing M. I got the following speed comparison (All in Release mode):

M = 10000: 0.17s
M = 20000: 0.67s
M = 30000: 1.49s
M = 40000: 2.65s
M = 50000: 4.14s
M = 60000: 5.96s
M = 65000: 6.98s

Code: Select all

int t3 = clock();
int M = 65000;
SparseMatrix<float> L(M, M);
L.reserve(M*5);
for (int j=0; j<M; j++){
      L.startVec(j);   
      for (int i=0; i<M; i++){
     if (abs(i-j)<=2)
       L.insertBack(i,j) = i+j;
      }
}
L.finalize();
int t4 = clock();
printf("Filling L : %.6lf seconds elapsed\n", ((double)t4-t3)/CLOCKS_PER_SEC); 



ggael wrote:hm, that's weird because insertBack does roughly the same than std::vector::push_back. Are you sure that's not your code to compute the coefficients which is slow?

Mmh...

To benchmark insertBack() your inner most loop shout better be

Code: Select all

for (int i=j-2; i<j+2; i++){
  if (i>0 && i<M) {
    L.insertBack(i,j) = i+j;
  }
}

Cheers
Frank

Mmm, that does improve a lot in this example. And the improvement is HUGE!! Why the performance is different ? From the tutorial, it was said the inner loop should be:

for each i interacting with j // with increasing i
mat.insertBack(i,j) = foo(i,j);

I never understand what is "interacting with", is your inner loop the correct way to "interact with"?

Thanks@@!!

FMD wrote:Mmh...

To benchmark insertBack() your inner most loop shout better be

Code: Select all

for (int i=j-2; i<j+2; i++){
  if (i>0 && i<M) {
    L.insertBack(i,j) = i+j;
  }
}

Cheers
Frank

Thank you so much. Now filling both A (60000x60000) and B and solve for A*x = B only takes 1 second even on my **** laptop!!!!!

Thank you again. Eigen is AWESOME!!!

FMD wrote:Mmh...

To benchmark insertBack() your inner most loop shout better be

Code: Select all

for (int i=j-2; i<j+2; i++){
  if (i>0 && i<M) {
    L.insertBack(i,j) = i+j;
  }
}

Cheers
Frank

to be clear, in your initial example you evaluate "abs(i-j)<=2" 65000*65000 times that is indeed expensive. In general the inner loop should only iterate over the non zero you want to insert, not on all pairs of indices.