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. > > >

**References**:**[eigen] Some background about LDLT***From:*hauke strasdat

**Messages sorted by:**[ date | thread ]- Prev by Date:
**[eigen] Some background about LDLT** - Next by Date:
**[eigen] RotationBase times DiagonalMatrix** - Previous by thread:
**[eigen] Some background about LDLT** - Next by thread:
**[eigen] RotationBase times DiagonalMatrix**

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