n2k
Registered Member

Hi,
I just have a simple question. In the documentation of Eigen 3.1, it says that, for dense matrices: LDLT requires a SPsD matrix (http://eigen.tuxfamily.org/dox/TopicLin ... tions.html), while, for the sparse version, SimplicialLDLT requires a SPD matrix (http://eigen.tuxfamily.org/dox/TutorialSparse.html). Does the sparse version of LDLT requires strict SPD? So, if I have a sparse SPsD matrix, the only builtin option is BiCGSTAB right? Thanks! 
ggael
Moderator

hm, I think it should work too. You can still test solver.info()==Success after the factorization, and fall back to BiCGSTAB if needed.

alecjacobson
Registered Member

It seems like SimplicialLDLT is not working for symmetric positive semi definite input. Here's a small test program:
The hardcoded matrix is positive semidefinite (tested in matlab, too). The dense version of LDLT succeeds but the sparse SimplicialLDLT fails. Interesting if I create a "dense" sparse matrix (insert 0 elements) then SimplicialLDLT succeeds. Hope this helps track down this issue. It would be great to have an LDLT that works on positive semidefinite sparse matrices. 
ggael
Moderator

There is a major difference between the dense and sparse LDL^T factorization: in the dense version we perform numerical pivoting while the sparse version performs fillin reducing pivoting. It seems that for this particular example the fillin pivoting does a bad job on the numerical side that is why disabling fillin pivoting make it work, but that's just luck. For another matrix it might be the opposite. As a workaround, the SparseLU solver does numerical column pivoting.
BTW, note that you can convert NAF to NA with NA = NAF.sparseView(); EDIT: after fillin ordering the matrix looks like:
which is pretty bad! There must exist a way to make the fillin ordering numerically more robust. 
ggael
Moderator

For the record, a few months back, I've improved this aspect by making AMD reordering aware of structural zeros: https://bitbucket.org/eigen/eigen/commits/ce076b6d66ce
The example given above by alecjacobson does work now. There is also a respective bug entry: http://eigen.tuxfamily.org/bz/show_bug.cgi?id=751 
matthieun
Registered Member

Hi everyone,
Gaël, does it mean that SimplicialLDLT should now (version 3.2.5) work on any symmetric positive semidefinite matrix? I just tried and got an error... I took a symmetric positive definite matrix (for which the factorization is working) and I cleared a row and a col to make it semidefinite. Is it a (bad) special case? Thanks. 
ggael
Moderator

No, it still does not work on problems with null eigenvalues, but it now properly handles problems of the form:
with A SPD, and C of rank row(C). The example provided by Alec is of this form, but such problems are usually not positivesemidefinite as they have both positive and negative eigenvalues, but they are invertible. 
Registered users: Bing [Bot], Felix Ernst, Google [Bot], markhm, mrperfecttt, shyamns, Sogou [Bot], Yahoo [Bot], zaydplays