Re: [eigen] LDLt and LLt fixes

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]


Hello,

As Benoit said, LDLt with D diagonal is unstable for indefinite symmetric matrices, as illustrated by the matrix

 0  1
 1  0

However, there is a well-known way to fix this: allow D to have 2x2 blocks on the diagonal (see e.g. Section 4.4 in Golub & Van Loan). This makes the factorization of the above matrix trivial. This is also what the DSYTRF routine in Lapack is doing (according to the documentation; I didn't actually check this).

The advantage of LDLt above LU is that it requires 1/3 n^3 flops instead of 2/3 n^3, so it's potentially twice as fast. I think stability is comparable to LU with partial pivoting. I seem to remember though that Keir Mierle said that the implementation is not that easy though.

Cheers,
Jitse



Mail converted by MHonArc 2.6.19+ http://listengine.tuxfamily.org/