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 1563 - Specific input to sparse QR solve produces erroneous result
Summary: Specific input to sparse QR solve produces erroneous result
Status: NEW
Alias: None
Product: Eigen
Classification: Unclassified
Component: Sparse (show other bugs)
Version: 3.3 (current stable)
Hardware: All All
: Normal Unknown
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2018-06-26 17:46 UTC by Jeff Trull
Modified: 2018-06-27 05:59 UTC (History)
3 users (show)



Attachments
minimal test case (1.72 KB, text/x-c++src)
2018-06-26 17:46 UTC, Jeff Trull
no flags Details
Improved test case (2.09 KB, text/x-c++src)
2018-06-27 03:04 UTC, Jeff Trull
no flags Details

Description Jeff Trull 2018-06-26 17:46:27 UTC
Created attachment 864 [details]
minimal test case

While running sparseqr_1 I stumbled across a (literally) one in a million bug. This input matrix:

[    10.875,          0,          0,          0,          0;
  -0.397597,    12.1403,          0,          0,  0.0317254;
  -0.851737, -0.0269339,    11.3113,  0.0130592,          0;
  -0.676106,          0,   0.138752,    8.57745,          0]

when factored and solved for:
[ 10.3612;
 -2.27836;
 -10.3179;
 -7.49344]

produces dramatically different results between dense and sparse implementations.
Comment 1 Jeff Trull 2018-06-27 03:03:53 UTC
I modified the bug title to more accurately express the problem, which is that the solve result from sparse QR cannot be used to recover the original RHS, i.e.

x = A\b
A*x is nowhere close to "b"

Dense QR and SuiteSparseQR produce different solutions as well but they can successfully recover "b".
Comment 2 Jeff Trull 2018-06-27 03:04:32 UTC
Created attachment 865 [details]
Improved test case
Comment 3 Jeff Trull 2018-06-27 05:59:30 UTC
I did some additional investigation. The problem appears to originate in the COLAMD code. If I override the column permutation with either 1) the order from dense QR or 2) the order from SuiteSparse, I can produce the result each of them calculated, both of which can correctly recover b.

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