How to get the number of non zero elements per row/col?
Is there a way without using an iterator to get the number on NNZs per row / col?
I'd like to avoid the following construct:
(In case of many NNZ computation takes long)

int count=0;
SparseMatrix<double> mat(rows,cols);
for (int k=0; k<mat.outerSize(); ++k)
{
count=0;
for (SparseMatrix<double>::InnerIterator it(mat,k); it; ++it)
{
count++;
}
//do something with count!
}

BTW: is InnerIterator tread safe?
I tried to manually parallize the outer for loop with openmp and it got stuck after a while.

You can call the nonZeros() method, e.g.: mat.outerVector(j).nonZeros()

InnerIterator should be be thread safe, of course as long as threads are not sharing the same iterator!

Code: Select all

 e.g.: mat.outerVector(j).nonZeros()

outerVector(j) is in my Eigen version not supportet.
Did you mean innerVector(j)?

Is this for both rows and cols doable without converting the storage order of a matrix?

right, I meant innerVector() which is an alias for col() for column-major, and row() for row-major. If you want the nnz of the row of a column-major matrix, then the cost of of the order of the number of non zeros of the entire matrix. We could provide a method returning a vector of the number of nonzeros of all rows, or all columns though.

>We could provide a method returning a vector of the number of nonzeros of all rows, or all columns though

This would be good!
Currently I've a sparse matrix with a high sparsity. For some further computation I only need to know which cols and rows have some non-zero entries.
Hence the vector (for each dimension) would be a good option; At best without reordering the entire matrix.

>If you want the nnz of the row of a column-major matrix, then the cost of of the order of the number of non zeros of the entire matrix.
Does this imply that the whole matrix has to be reordered which includes temporary an additional matrix of the same size?

>We could provide a method returning a vector of the number of nonzeros of all rows, or all columns though.
My work-arround solution is similar to your suggestion. But with the cost of iteration once over all NNZ and storing the results of .col() & .row() evaluation in corresponding row/column vectors. Maybe this is not the most effective way.

Let's say that the matrix is a NxN columns major sparse matrix with M non zeros, then the nnz per column could be obtain in O(N), (O(1) for one column by computing index differences), while the nnz per row is O(M) : there is no faster solution than iterating over all non zeros and accumulating them in a vector of size N.

Your assumption (NxN) is a little easier than mine; I use a MxN matrix with NNZ non zeros.
I've to spend a little more effort for initializing and accumulating the result vectors. (It seems to work...)

Code: Select all

 
       Eigen::VectorXd  NNZcol(statespace);
       Eigen::VectorXd  NNZrow(statespace);
        for (int k=0; k<myMTX.outerSize(); ++k)
        {
                 NNZrow(k)=0;
                 NNZcol(k)=0;
        }
        for (int k=0; k<myMTX.outerSize(); ++k)
         for (spmatrix::InnerIterator it(myMTX,k); it; ++it)
         {
                NNZcol(it.col()) +=1;   // row index
                NNZrow(it.row()) +=1;  // col index (here it is equal to k)
         }
        long ColCnt=0;
        long RowCnt=0;
        for (int k=0; k<myMTX.outerSize(); ++k)
        {
                 if(NNZrow(k)!=0)
                   RowCnt++;
                 if(NNZcol(k)!=0)
                   ColCnt++;
        }


I don't see any difference between NxN or NxM. In your code, two loops can be omitted:

VectorXi NNZcol = VectorXd::Zero(myMTX.cols());

Note the VectorXi instead of a vector of double. You can also do:

NNZcol.setZero(); // does not change the size
NNZcol.setZero(myMTX.cols()); // resize and set to 0

And for the last one:

RowCnt = NNZrow.cast<bool>().count();

>I don't see any difference between NxN or NxM.
True, I submitted the first version; sorry now the latest:

Code: Select all

 
  Eigen::VectorXd  NNZcol(myMatrix.outerSize());
  Eigen::VectorXd  NNZrow(myMatrix.innerSize());

  for (int k=0; k<myMatrix.outerSize(); ++k)
  {
     NNZcol(k)=0;
  }

  for (int k=0; k<myMatrix.innerSize(); ++k)
  {
     NNZrow(k)=0;
  }

  for (int k=0; k<myMatrix.outerSize(); ++k)
   for (spmatrix::InnerIterator it(myMatrix,k); it; ++it)
   {
                it.row(); // row index
                it.col(); // col index (here it is equal to k)

                NNZcol(it.col()) +=1;
                NNZrow(it.row()) +=1;
   }

   for (int k=0; k<myMatrix.innerSize(); ++k)
   {
                 if(NNZrow(k)!=0)
                   rowinst++;
   }

   for (int k=0; k<myMatrix.outerSize(); ++k)
   {
                 if(NNZcol(k)!=0)
                   colinst++;
   }
   NNZrow.resize(0,0);
   NNZcol.resize(0,0);


>Note the VectorXi instead of a vector of double.
I had two ways in mind first was counting the NNZ the second was accumulating the values (which are of type double).

>RowCnt = NNZrow.cast<bool>().count();
This I did not understand; I noticed in the documentation that count() counts all NNZ elements the cast is from me not clear.

right, the cast is implicit, so you can omit it.

So let me summarize your suggestions:

Code: Select all

VectorXi NNZcol = VectorXd::Zero(myMatrix.outerSize());
VectorXi NNZrow = VectorXd::Zero(myMatrix.innerSize());

  for (int k=0; k<myMatrix.outerSize(); ++k)
   for (spmatrix::InnerIterator it(myMatrix,k); it; ++it)
   {
                it.row(); // row index
                it.col(); // col index (here it is equal to k)

                NNZcol(it.col()) +=1;
                NNZrow(it.row()) +=1;
   }
RowCnt = NNZrow.cast<bool>().count();
ColCnt = NNZcol.cast<bool>().count();

NNZrow.setZero(); // resize and set to 0
NNZcol.setZero(); // resize and set to 0
NNZrow.resize(0,0);
NNZcol.resize(0,0);


>NNZcol.setZero(); // does not change the size
>NNZcol.setZero(myMTX.cols()); // resize and set to 0
The last one I didn't find in the documentation and it's not clear for me.

To be clear, here are 3 different version of creating a vector filled with '0's:

Code: Select all

VectorXi NNZcol = VectorXd::Zero(n);


Code: Select all

VectorXi NNZcol(n);
NNZcol.setZero();


Code: Select all

VectorXi NNZcol;
NNZcol.setZero(n);


that's all I wanted to say!

>To be clear, here are 3 different version of creating a vector filled with '0's:
OK, now I got it; sometimes it takes a while ...