New user self-registration is currently disabled. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Bug 792 - SparseLU::factorize crashes with error: "Assertion `index >= 0 && index < size()' failed."
SparseLU::factorize crashes with error: "Assertion `index >= 0 && index < siz...
Status: RESOLVED FIXED
Product: Eigen
Classification: Unclassified
Component: Sparse
3.2
x86 - 64-bit Linux
: Normal Unknown
Assigned To: Nobody
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2014-04-11 20:45 UTC by renshaw
Modified: 2015-07-26 18:51 UTC (History)
2 users (show)



Attachments
program illustrating the problem (561 bytes, text/x-c++src)
2014-04-11 20:45 UTC, renshaw
no flags Details
Patch to fix SparseLU crashes on singular matrices (756 bytes, patch)
2015-07-23 14:04 UTC, simon.floery
no flags Details | Diff

Description renshaw 2014-04-11 20:45:04 UTC
Created attachment 451 [details]
program illustrating the problem

Compile and run the attached program, which constructs a 10 x 10 sparse matrix and then attempts to compute an LU factorization. It prints out:

Nonzero entries:
(1,1) (-1,1)

Outer pointers:
0 0 1 1 2 2 2 2 2 2 $

0 0 0 0 0 0 0 0 0 0 
0 1 0 -1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0

a.out: eigen/Eigen/src/Core/DenseCoeffsBase.h:412: Scalar &Eigen::DenseCoeffsBase<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 1>::operator()(Index) [Derived = Eigen::Matrix<int, -1, 1, 0, -1, 1>, Level = 1]: Assertion `index >= 0 && index < size()' failed.



According to gdb, the value of `index` at the time of failure is 6684880.

The problem can be traced to the pivotL() function in SparseLU_pivotL.h. The `lsub_ptr` variable points to uninitialized memory. We detect that the matrix is singular, and then we try to lookup perm_r(pivrow), where pivrow is read from the uninitialized memory. Line 90:

if ( pivmax == 0.0 ) {
    pivrow = lsub_ptr[pivptr];
    perm_r(pivrow) = jcol;
    return (jcol+1);
  }



This behavior is present in revision 5877:732325de4d56.
Comment 1 renshaw 2014-04-11 21:05:52 UTC
(This issue was found as part of the ASTAA robustness testing project.)
Comment 2 simon.floery 2015-07-23 14:04:30 UTC
Created attachment 592 [details]
Patch to fix SparseLU crashes on singular matrices

Attached patch against eigen-3.2.5 lets SparseLU recover from singular input matrices. For singular matrices as simple as [1 0 0; 0 1 0; 0 0 0], lsub_ptr[pivptr] in line 91 is unintialized and may crash the method.

The patch is based on a patch from the SciPY project [1]. For a list of SciPy's changes to SuperLU see [2].

Regarding some more background information, SciPy's patch itself seems to be based on an ifdef'ed work-around in SuperLU's original source code that appears with version 4.0. See also SuperLU_4.3/SRC/dpivotL.c.

best, simon

[1] https://github.com/scipy/scipy-svn/commit/f11539e6eaa29cae09a0bd7c0bdf5b4ecd8d82fd
[2] https://github.com/scipy/scipy-svn/blob/master/scipy/sparse/linalg/dsolve/SuperLU/scipychanges.txt
Comment 3 Christoph Hertzberg 2015-07-26 18:51:34 UTC
Thank you for looking into this.
I pushed a fix, based on your patch, as well as a unit test to the stable and devel-branch:
https://bitbucket.org/eigen/eigen/commits/a02453e
https://bitbucket.org/eigen/eigen/commits/e8733e5

Unfortunately, column-ordering still crashes for (structurally) rank-deficient matrices. I opened Bug 1045 for that.

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