| Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Tue, 23 Feb 2010 16:11:58 -0500
- 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; bh=VWIX7WkpePPzwA/ZUy9+3Jt1RJtSZtlqJstuSOKsUn4=; b=DrpQJuxnZL4MTUMnwQNVFC5S1rwylb6ICjhG50KEO6ACrhENv0pSJL6kCvo7KgB+9x TKJlAuHT+OYOL4e/8KDOA229gAJuwTKgectLXrTdOfKb/7VkpVDuCJSbmy92LEXinSxK PL2YxP033bIE2kc8BVj5hVFU8kydtWe8KnkWY=
- 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; b=ax5dWUBPWJAm397RbXz6VY35iz+YAQE1MoVFMYZ78oeZr+ND4uMLhApIqWlmQ3OvAZ +MwFS7RtiJlOfVagI2VAOhn19UvVVLaNH6clMlmZTlpCmRkT0IzReAQJQxwrNjUWD1LR U1PqzKKTc1RfbFgJOWHgEBhdceRaHdXyh/DoA=
Hi Ben,
Thanks for your great test-case. It helped a lot. Thanks also for the
patch, but i didn't apply it, because the problems were deeper:
Normally, when we terminate without 'finalizing' the matrix, that's
because our termination criterion tells us that the remaining block of
the matrix is approximately zero anyway.
Unfortunately, there were 2 bugs in our code. Fixing either of them
was enough to make your test-case happy.
The first bug was that our second termination criterion didn't
actually say that the remaining block is zero. So it didn't tell us
that we could safely terminate. The fix was to quit using it as a
termination criterion, and only use it as a criterion to do the
division by Djj.
The second bug was that our cutoff was too big. It came from Higham's
formula that tells how to choose a cutoff for optimal rank
determination, but here in LDLt we're not even trying to be
rank-revealing. So a small cutoff (using machine precision) is better,
it gives better accuracy as it prevents triggering termination
criteria too early.
Both bugs fixed in the development branch.
Thanks,
Benoit
2010/2/22 Ben Goodrich <bgokgm@xxxxxxxxxxxxxx>:
> Hi,
>
> Thank you for creating eigen. It is great.
>
> I mentioned a bug about ldlt() with rank-deficient matrices and gave a
> test case here:
>
> http://forum.kde.org/viewtopic.php?f=74&t=85449&sid=43724496b3e1705a95b41fa17c0f95eb&start=10
>
> I believe the problem is that when ldlt() decides to abort due to a
> diagonal entry of D being too close to zero, it does not change the
> remaining diagonal entries to be 0.0 . As a result, when the original
> matrix has a nullity of 2 or more, multiplying the factors together
> does not result in the original matrix.
>
> The attached patch fixes this issue for me in the test case by zeroing
> out the relevant diagonal entries. It applies to the development
> branch. I will reply to this message with a patch and a question about
> the stable branch.
>
> Thank you,
> Ben
>