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*: Keir Mierle <mierle@xxxxxxxxx>*Date*: Fri, 30 Jan 2009 09:23:50 -0800*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=rjC1Pf7S4b1+sm54wcds29XF0/c20sFn1kSqEbUnt+0=; b=i4atfqLx1rrhMHy+Iev88axRigHQO/tTcfQdhSnSiQVuiezZ6b3tnwKVWmHjnOalpY bwQ8e2RjMfQYv1OyduEoQkyIrZTrnGLjQmGAcWnk4KC/xqtI+swSJA8YMbeh+iapHLZ6 CEx5foFnyUi/bCLPumDpEzseYfKrvxScWCAhE=*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=Nxt3UUqCiTI3my/sR2EVBGVAWSiaj5a47HFUCic9GTPg0d8LYo02mN7ZpC8qVSp5GI yNjclK4btF42bcbFilE1q2X618DbEjvmaHdM6/ZNJlPdsqdcwcSmJdINbLUYahD2ry0E wv9r0Me+paAR4ATIxx7cK1/lN87eNJU8L07+I=

Hi, I am working on a pivoting variant of the LDLt, but it doesn't seem that the algorithm matches the formula on the wikipedia page http://en.wikipedia.org/wiki/Cholesky_decomposition (see the section avoiding square roots). In particular, it doesn't appear the Dj is multiplied into the product. Where does this algorithm come from? 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 >>>>>> >>>>> >>>>> >>>>> >>>> >>>> >>>> >>> >>> >>> >> >> >> > > >

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

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

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Computing left nullspace of A when rows > cols** - Next by Date:
**Re: [eigen] Computing left nullspace of A when rows > cols** - 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/ |