New user self-registration is disabled due to spam. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Before reporting a bug, please make sure that your Eigen version is up-to-date!
Bug 875 - SparseMatrixBase<Derived>::nonZeros() is broken for most types of Derived
Summary: SparseMatrixBase<Derived>::nonZeros() is broken for most types of Derived
Status: RESOLVED FIXED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Sparse (show other bugs)
Version: 3.3 (current stable)
Hardware: All All
: Highest Crash
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks: 3.3
  Show dependency treegraph
 
Reported: 2014-09-12 11:25 UTC by Henrik Friberg
Modified: 2015-04-01 22:34 UTC (History)
2 users (show)



Attachments

Description Henrik Friberg 2014-09-12 11:25:01 UTC
The call to nonZeros() on a SparseSparseProduct object leads to an infinite recursion smacking the stack. This can be seen by running valgrind with the verbose "-v" parameter on the following example:

---------------------
#include "Eigen/SparseCore"
#include <iostream>

using namespace Eigen;

typedef SparseMatrix<double, ColMajor> SpMat;

int main(int argc, char **argv)
{
    const int m = 3;

    SpMat A(m,m);
    A.insert(0,0) = 1.0;
    A.insert(1,1) = 2.0;
    A.insert(2,2) = 3.0;
    A.makeCompressed();

    SpMat B(m,m);
    B.insert(0,0) = 1.0;
    B.insert(1,1) = 2.0;
    B.insert(2,2) = 3.0;
    B.makeCompressed();

    int nnz = (A * B).nonZeros();

    std::cout << nnz << std::endl;
}
---------------------
Comment 1 Christoph Hertzberg 2014-10-14 13:22:42 UTC
Another thing that is broken is TriangularView<SparseMatrix>.
This leads to an infinite recursion in many sparse_product unit tests.
Strangely, clang++ optimizes away the recursion if compiled with optimization enabled and returns -1 (maybe that value is just by accident). With optimization, g++ generates a trivial infinite loop, leading to a time-out in the unit-tests.

Are there any cases except SparseMatrix<>, (and maybe Map<SparseMatrix>, Transpose<SparseMatrix>) where nonZeros() can be determined directly? I.e. does it make sense to provide a nonZeros() from SparseMatrixBase?
Comment 2 Christoph Hertzberg 2014-10-28 13:33:36 UTC
I pushed a work-around to avoid the infinite recursion:
https://bitbucket.org/eigen/eigen/commits/9a59ef56ef
This make the sparse_product unit tests pass again.

We still need to decide if it makes sense to provide nonZeros() for other than "direct access" sparse matrices.
Comment 3 Gael Guennebaud 2014-10-28 17:26:47 UTC
Having an estimate of the nnz is really useful in sparse algorithms, even if it is not  100% accurate. Having nonZeros() be sometimes accurate and sometimes only an approximation is probably not very good. So, since this is essentially needed for evaluation purposes, this information could be carried out by evaluators. Evaluators should also be able to return a more accurate information when some sub-expressions are evaluated into temporaries.
Comment 4 Christoph Hertzberg 2014-10-28 17:49:29 UTC
Would it be too late to remove nonZeros() from SparseMatrixBase and only implement it for SparseMatrix (and Map<SparseMatrix>) directly (or maybe a common base class of them)?
I guess for all (?) other cases the only way to get the exact number of nonZeros basically requires to evaluate the expression.
nonZeros() has been in SparseMatrixBase at least since 2010, however it likely never worked correctly, other than for the "direct access" matrices.
Alternatively, we could deprecate it and/or let it static_assert if it is not implemented.

Regarding the approximated nnz, I guess we don't need to expose an estimateNonZeros() to the public interface, so implementing this as internal evaluator functionality sounds good to me.
Comment 5 Gael Guennebaud 2015-04-01 22:34:25 UTC
Removing the broken nonZeros() method from SparseMatrixBase is the only reasonable option.


https://bitbucket.org/eigen/eigen/commits/2c7c12495212/

Summary:     Bug 875: remove broken SparseMatrixBase::nonZeros and introduce a nonZerosEstimate() method to sparse evaluators for internal uses.
Factorize some code in SparseCompressedBase.

Note You need to log in before you can comment on or make changes to this bug.