| 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: Wed, 28 Jan 2009 17:45:49 +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=uGo9LbVohhalhLBXj072wtZRXLIcAjdiA3Gg3pPqsbY=; b=MohuSBufYiOK5Iu4Tt82lBI+Lin8cJAxcDOU/u3HhegenpveuG5RADj0/GOtxR15I3 t0dKdtONLQojHIm2vuBqIHvJkNRocTHvQOrxNwVLboSgwnSn0+JelB5oAT4h6ZyBnETe r6/dyWgwKwJoIPWKaSOyXQ+hWI+GEjZCJyyV8=
- 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=qv7tvaiAKDD4prdSzaY+q77OvTJfHhX6zfPPS8xgZsa/KUE9Fez7WI3yqp7EBKW2X3 pIgJNtpi50rARInF5JORDqzAs/VdXY+2YFxb+H8y1/liWvoXqEw530OysctiBVB7QNem lVOE+wMsNjyZk50BcTOzY5Krwy6d5QUTkrdX4=
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
>>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>
>>
>>
>
>
>