Re: [eigen] Instability in LLT and LDLT methods. |

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

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] Instability in LLT and LDLT methods.*From*: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>*Date*: Fri, 30 Jan 2009 22:52:07 +0100*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=dNtuBFMbafp90Pcyb1bNcTMWNbdSmY0D7paazgJK8PQ=; b=ZN3Rn6S0QD2KLJSypLrirv+7gagW90Nvk3nefpV4idWj79QYL6C4ZfHqisasCyC8E4 6WAVzhFzN51WNxA0dVXIiliVuW1r6zy6EKuGoVigKWzcofrYLehoWptI38tUTG0akSSd TxnwUEUAve052/BNcC1zt0y0xV/0Vp+PlmB+c=*Domainkey-signature*: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=RaKWQiamlHL68/jsJ8hVmi2Vo2DoyO8obpBYM3tBVzH4lDNtt58WS86vMvQmrNwfco AwHF40h0j87TJuJMa+S2KPIH/0ZT5RlDwUNBkIyqq4iucS5XvMU6GIEccYfXkn8YJK9l VkwLKIDOz4UplVQ7hEzgIv5dA/4UWRCmrFhBU=

Hi, I'm not sure to understand your concerns. The LDLt algo on wikipedia is the one currently implemented in Eigen, i.e., without pivoting. On Fri, Jan 30, 2009 at 6:23 PM, Keir Mierle <mierle@xxxxxxxxx> wrote: > In particular, it doesn't appear the Dj is multiplied into the > product. Where does this algorithm come from? which one ? hm... do you mean the algo of the link in the forum looks weird ? then that might be the case, I did not checked it at all. > Keir > > On Wed, Jan 28, 2009 at 8:45 AM, Gael Guennebaud > <gael.guennebaud@xxxxxxxxx> wrote: >> see this thread: >> http://forum.kde.org/solved-lu-only-half-as-fast-as-lapack-t-28265-2.html#pid38539 >> there is a link to source code under BSD license. >> >> that's all I have :( >> >> good luck ! >> >> On Wed, Jan 28, 2009 at 5:34 PM, Keir Mierle <mierle@xxxxxxxxx> wrote: >>> I'm working on this now (pivoting in LDLt). Do you have a reference >>> for the algorithm used? It's pretty simple but a reference would help. >>> >>> Keir >>> >>> On Tue, Jan 27, 2009 at 11:42 PM, Gael Guennebaud >>> <gael.guennebaud@xxxxxxxxx> wrote: >>>> yes, indeed with LDLt we could do full pivoting and be as stable as LU >>>> for selfadjoint matrices while being faster. My initial motivation >>>> with LDLt, however, was its performance because it avoids the square >>>> roots... On the other hand, I remember my benchmark was not really in >>>> favor of the current LDLt,. I have to check again, but if so, then >>>> there is no reason not to keep the current LDLt version which could be >>>> replaced by a more complex one with full pivoting. >>>> >>>> On Wed, Jan 28, 2009 at 12:43 AM, Keir Mierle <mierle@xxxxxxxxx> wrote: >>>>> Probably it's better to do full pivoting. Apparently cholesky is >>>>> stable for semidefinite matrices when full pivoting is used: >>>>> >>>>> http://eprints.ma.man.ac.uk/1101/01/covered/MIMS_ep2008_56.pdf >>>>> >>>>> Keir >>>>> >>>>> On Tue, Jan 27, 2009 at 3:05 PM, Gael Guennebaud >>>>> <gael.guennebaud@xxxxxxxxx> wrote: >>>>>> Hi, >>>>>> >>>>>> yes, it seems the test to check whether the matrix is positive >>>>>> definite was too strict. I changed the absolute tolerance a bit, but >>>>>> we still need something better. Basically, in Cholesky we compute at >>>>>> each iteration 1/sqrt(x), and so x must be >0 with some epsilon... >>>>>> >>>>>> Gael. >>>>>> >>>>>> On Tue, Jan 27, 2009 at 7:35 PM, Keir Mierle <mierle@xxxxxxxxx> wrote: >>>>>>> Here is a testcase that fails with LLT and LDLT but works fine with >>>>>>> all of LU, SVD, and QR solving. Depends on my previous patch for QR >>>>>>> solver (or comment out the qr().solve line). >>>>>>> >>>>>>> Keir >>>>>>> >>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>>> >>>> >>>> >>>> >>> >>> >>> >> >> >> > > >

**References**:**[eigen] Instability in LLT and LDLT methods.***From:*Keir Mierle

**Re: [eigen] Instability in LLT and LDLT methods.***From:*Gael Guennebaud

**Re: [eigen] Instability in LLT and LDLT methods.***From:*Keir Mierle

**Re: [eigen] Instability in LLT and LDLT methods.***From:*Gael Guennebaud

**Re: [eigen] Instability in LLT and LDLT methods.***From:*Keir Mierle

**Re: [eigen] Instability in LLT and LDLT methods.***From:*Gael Guennebaud

**Re: [eigen] Instability in LLT and LDLT methods.***From:*Keir Mierle

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Multiarray** - Next by Date:
**Re: [eigen] Totally missing /O2 for MSVC-Compiler** - Previous by thread:
**Re: [eigen] Instability in LLT and LDLT methods.** - Next by thread:
**Re: [eigen] Instability in LLT and LDLT methods.**

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