| Re: [eigen] Some background about LDLT |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Some background about LDLT
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Tue, 26 Jul 2011 10:07:09 -0400
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; bh=cS+ebKS2mbws0XMXjps9I+cwM8vy5kcxBQ01t6wM2h4=; b=pP5jz/zf5sP2my0doD4fTxYfd2uykTLQQQXZJiPgpON78k9EJBAfF+EsVu+dFCdj/f yLiFyZEAn54PokA2KALH0Q5NKT85Itpk+8ANk8/qCIHPABHskfJW8W3qahUJ4bCuUvvi kL2BWG4fEuMHa7xdy5+jfG9zAl53+9a0PGvwc=
2011/7/26 hauke strasdat <strasdat@xxxxxxxxx>:
> Hi,
>
> I am using the LDLT method
> (http://eigen.tuxfamily.org/dox/classEigen_1_1LDLT.html) 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:
http://en.wikipedia.org/wiki/Cholesky_decomposition#Avoiding_taking_square_roots
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:
http://icl.cs.utk.edu/news_pub/submissions/ldlt.pdf
>
> 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 http://icl.cs.utk.edu/news_pub/submissions/ldlt.pdf shows
component-wise error on a variety of test matrices.
> - What is the speed/accuracy table
> (http://eigen.tuxfamily.org/dox/TutorialLinearAlgebra.html) based on.
It's based on our understanding of these algorithms and our experience
with them.
Benoit
>
> Thanks a lot in advance,
> Hauke S.
>
>
>