New user self-registration is disabled due to spam. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Bug 1150 - crash when using IncompleteCholesky preconditioner
Summary: crash when using IncompleteCholesky preconditioner
Status: RESOLVED FIXED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Sparse (show other bugs)
Version: 3.3 (current stable)
Hardware: All All
: Normal Crash
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2016-01-20 14:42 UTC by fabien chêne
Modified: 2016-01-27 14:51 UTC (History)
2 users (show)



Attachments
testcase (645 bytes, text/plain)
2016-01-20 14:42 UTC, fabien chêne
no flags Details

Description fabien chêne 2016-01-20 14:42:19 UTC
Created attachment 646 [details]
testcase

The attached testcase crashes when compiled without NDEBUG on this assertion:

IncompleteCholesky.h:155: void Eigen::IncompleteCholesky<Scalar, _UpLo, _OrderingType>::_solve_impl(const Rhs&, Dest&) const [with Rhs = Eigen::Matrix<double, -1, 1>; Dest = Eigen::Matrix<double, -1, 1>; Scalar = double; int _UpLo = 1; _OrderingType = Eigen::AMDOrdering<int>]: Assertion `m_factorizationIsOk && "factorize() should be called first"' failed.

With N < 10, the assertion does not trigger.
Comment 1 Gael Guennebaud 2016-01-20 18:12:43 UTC
This is because the solver failed, as reported by:

solver.info()

and more precisely, the preconditioner failed to factorize the matrix:

solver.preconditioner().info()


Of course, ILLT should not fail on a SPD matrix, so let's see what's going wrong.
Comment 2 Gael Guennebaud 2016-01-20 18:34:19 UTC
OK, so we probably need to restart with a larger shift until the factorization succeed, as in algorithm 3.1 of: http://ftp.mcs.anl.gov/pub/tech_reports/reports/P682.pdf

Should be straightforward. Patch welcome ;)
Comment 3 Gael Guennebaud 2016-01-23 21:40:49 UTC
https://bitbucket.org/eigen/eigen/commits/08afec829f35/
Summary:     Bug 1150: make IncompleteCholesky more robust by iteratively increase the shift until the factorization succeed (with at most 10 attempts).
Comment 4 fabien chêne 2016-01-26 10:03:57 UTC
(In reply to Gael Guennebaud from comment #3)
> https://bitbucket.org/eigen/eigen/commits/08afec829f35/
> Summary:     Bug 1150: make IncompleteCholesky more robust by iteratively
> increase the shift until the factorization succeed (with at most 10
> attempts).

Thanks for fixing it. Is there still a risk of failure with the shift increment strategy ? If yes, would it occur on specific cases like big matricies, ill conditioned matricies, ... ?
Comment 5 Gael Guennebaud 2016-01-27 14:51:17 UTC
Yes there is still a risk (e.g., with a large negative eigenvalue). It performs a maximum of 10 iteration, doubling the shift each time. If it still fails, you can increase the initial shift with the respective method, but with such a large shift, better use another preconditioning technique.

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