This bugzilla service is closed. All entries have been migrated to https://gitlab.com/libeigen/eigen
Bug 792 - SparseLU::factorize crashes with error: "Assertion `index >= 0 && index < size()' failed."
Summary: SparseLU::factorize crashes with error: "Assertion `index >= 0 && index < siz...
Status: RESOLVED FIXED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Sparse (show other bugs)
Version: 3.2
Hardware: x86 - 64-bit Linux
: Normal Unknown
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-04-11 20:45 UTC by renshaw
Modified: 2019-12-04 13:13 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.
Comment 4 Nobody 2019-12-04 13:13:29 UTC
-- GitLab Migration Automatic Message --

This bug has been migrated to gitlab.com's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.com/libeigen/eigen/issues/792.

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