| 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: Wed, 28 Jan 2009 08:34:01 -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=bVVGYe98Q/1mMMZAxoOpqaBUriQjauvnj5HD8wgsxks=; b=ceDP0k1dg+v1elDMyXL+CkMrY5g9Q1UtyAbfB0X3nsk+gU5ofkFvoLJnvPaXw8urZz sYXv70R25DrpMyVAIh7E6M06qRMoWilNPz97a8Pkt/nPMXydqv/EEtX9w0eF4RQflM6k fo2RqV+nmGbMZhRkQy3gNYVz78thQbOPrNAvg=
- 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=l3Py8yCHPXmxBT++dz4alu6EeTv/JX6YFEGYhj359WMuYzNNhQQQrF/LtQTckFKLLl H8mLoGHzznWDxnnr9CO/9U8lxrltyZl/TtqWrfv8iVXMh7gTGXBXHxj5n3mOEkZh17vk uxw9kUAHsxQo7RhmZQ1R/xjwg8h6xgtQBb4KQ=
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
>>>>
>>>
>>>
>>>
>>
>>
>>
>
>
>