This bugzilla service is closed. All entries have been migrated to https://gitlab.com/libeigen/eigen
Bug 657 - LevenbergMarquardt - lmqrsolv ignores zero entries
Summary: LevenbergMarquardt - lmqrsolv ignores zero entries
Status: NEW
Alias: None
Product: Eigen
Classification: Unclassified
Component: Unsupported modules (show other bugs)
Version: 3.2
Hardware: All All
: Normal Unknown
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-09-16 11:45 UTC by simon.floery
Modified: 2019-12-04 12:37 UTC (History)
0 users



Attachments
lmqrsolve_dont_ignore_zeros.patch (1.76 KB, patch)
2013-09-16 11:45 UTC, simon.floery
no flags Details | Diff

Description simon.floery 2013-09-16 11:45:44 UTC
Created attachment 383 [details]
lmqrsolve_dont_ignore_zeros.patch

Hi,

There is a flaw in the sparse version of lmqrsolv in unsupported's LevenbergMarquardt module that makes the optimization assert with 

Eigen/src/SparseCore/TriangularSolver.h:78: static void Eigen::internal::sparse_solve_triangular_selector<Lhs, Rhs, Mode, 2, 1>::run(const Lhs&, Rhs&) [with Lhs = Eigen::Block<Eigen::SparseMatrix<double, 1>, -1, -1, false>; Rhs = Eigen::Matrix<double, -1, 1>; int Mode = 2]: Assertion `it && it.index()==i' failed.

in certain cases. lmqrsolv iterates and updates only the non-zero entries in R, which does not suffice. Attached patch provides a fix, though in a trivial and  less than optimal way.

Unfortunately, I do not have the time to go through the theory to see, which zero entries must not be ignored. Please let me know if I can assist in testing.

best, simon
Comment 1 simon.floery 2013-09-17 17:15:52 UTC
Just some background information:

The original documentation in MINPACK gives some more insight into lmqrsolv, for example at http://www.netlib.no/netlib/sminpack/qrsolv.f. The task is to solve a system of linear equations A*x=b with A=(B*P|D*P)^T composed of 
* a matrix B, for which we computed a QR factorization before 
* and a (permuted) diagonal matrix D.
The current implementation updates the QR factorization of B by Givens rotation to a QR factorization of entire A.

Does this update by Givens rotations make sense for a sparse matrix? Or would it be better to compute a fresh QR decomposition for A with SparseQR?

best, simon
Comment 2 Nobody 2019-12-04 12:37:13 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/657.

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