New user self-registration is disabled due to spam. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Bug 694 - Handling unordered sparse matrices (as in SparseQR::matrixR)
Summary: Handling unordered sparse matrices (as in SparseQR::matrixR)
Status: DECISIONNEEDED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Sparse (show other bugs)
Version: 3.2
Hardware: All All
: High API Change
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks: 3.4
  Show dependency treegraph
 
Reported: 2013-10-29 08:31 UTC by Joel
Modified: 2016-02-01 15:46 UTC (History)
2 users (show)



Attachments

Description Joel 2013-10-29 08:31:31 UTC
The inner indices in the matrix returned by SparseQR::matrixR are unsorted.  This makes any componentwise binary operation (e.g. +) fail as it iterates over the indices.  

This appears to be trivially reproducible: construct a sparse matrix; calculate it's QR; look at the inner indices.  If it's not, I'm happy to put together an example.
Comment 1 Gael Guennebaud 2016-02-01 15:44:57 UTC
I made it clear in the doc:

https://bitbucket.org/eigen/eigen/commits/314d8cb79f86/
Summary:     Bug 694: document that SparseQR::matrixR is not sorted.


Now, we need a proper fix to handle unordered sparse matrices. To this end, we need:

1 - a way to tell Eigen that a matrix has unordered entries: runtime flag (like the compressed state), or compile-time via the Option template parameter of SparseMatrix, or even via a decorator

2 - an easy and efficient way to a turn an unordered matrix into an ordered one: in-place sort, or via two transpositions.

3 - decide whether this conversion should be implicitly done on demand, e.g.: when evaluating A+B, if B is unordered, copy it to an ordered one.


Questions (1) and (3) are kind of related. For instance, if we go for a compile-time flag for (1), then it would be possible and ok to trigger a static assertion for (3), similar to the case of storage-order mismatch. On the other hand, if we go with with a runtime flag for (1), then we should probably go with implicit conversion for (3), similar to what we do regarding the compressed flag (some matrix decompositions require compressed entries). Indeed, a runtime assertion would not be welcome because a might easily missed that a matrix is unordered if not warned at compile-time.

We should come up with a solution for 3.4.

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