Re: [eigen] Some background about LDLT

[ Thread Index | Date Index | More Archives ]

2011/7/26 hauke strasdat <strasdat@xxxxxxxxx>:
> Hi,
> I am using the LDLT method
> ( on
> semi-definite matrices quite heavily and it is working well for me.
> However, I would like to learn some more about this very successful
> approach. I wonder, is there any good reference (preferably an
> academic paper) about it?

I don't think we followed any existing book, but this isn't new. LDLT
is described for example in this wiki page:

Then we added partial pivoting on top of it, working exactly as in the
partial-pivoting LU decomposition.

I'm sure there's literature on "pivoting LDLT"; anything carrying that
name would probably be exactly the same thing that we do. A google
search found this:

> In particular, I would like to know:
>  - The LDLT method differs from standard Cholesky by two features:
>   * The diagonal D.
>   * The pivoting P'LDL'P.

That's correct.

>  Is it correct to say that D is added for speed and accuracy reasons
> (avoid square root),

Yes, see above wikipedia link.

> while the pivoting is added to stabilise accuracy
> for rank deficient matrices (with a minimal cost overhead)?

Yes, correct. I think one can even come up with examples of
well-conditioned invertible matrices that benefit from pivoting, but
yes for the most part it's about nearly singular matrices.

>  - Is it possible/practical to use LDLT without pivoting on
> rank-deficient semi-definite matrices?

Depends if you can live with the numerical stability issues. Table 1
in shows
component-wise error on a variety of test matrices.

>  - What is the speed/accuracy table
> ( based on.

It's based on our understanding of these algorithms and our experience
with them.


> Thanks a lot in advance,
> Hauke S.

Mail converted by MHonArc 2.6.19+