| Re: [eigen] Pivoting for LDLT |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Pivoting for LDLT
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Mon, 2 Feb 2009 15:32:27 +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=wKxQxiEv86R/ajniMvOtLNkw/+nAwI2RNvdfk1WH1WA=; b=cDB+jpmF/pIkT82iTDctxB/qXK+oPNEwk067HOYVQLb/bUvq58cRRl5LOB3MnFx6GE sRFDmn2suq5hYjARaZTiQRqAPsJrB2AhS0F9fJiszqixIejGgpnFN4THroL5yiiY24tj +ZJshW2dEA7FQ+Vp6d+c+mlgkcfPmE1Knwl0I=
- 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=JT5C3aUaZACvS6EqpT+nqOkYOgCmGQqPSpgimkfC5apAlmL3w1aVAWgd+2GsGyndv0 RJSZJKhGrRAiFCopo4FkggGOmQyK2xiRzhWorVrmQR+21PxNSvHYaHcQfB/n65QwmarZ A3gfFRgWqU+TmFQOPrfW58kd4tKoJlEWBeu/g=
2009/2/2 Jitse Niesen <jitse@xxxxxxxxxxxxxxxxx>:
> On Mon, 2 Feb 2009, Keir Mierle wrote:
>
>> I implemented a simple pivoting strategy for LDLT, but am not convinced
>> it's better.
>>
>> It looks for the largest diagonal element during each iteration, then
>> pivots it to become the next processed row. Attached is a simple test that
>> compares the old LDLT vs the pivoting one; it shows that the results are not
>> fantastic. I find that there is consistently 30% or more residual in the
>> pivoting version.
>
> That surprises me.
>
> When I try it out on 100 random matrices of size 100 x 100, I get:
>
> Average residual: nopiv 4.45718e-14 piv 4.07206e-14
> Std.dev.: nopiv 1.43516e-15 piv 1.01811e-15
> Minimum: nopiv 4.09651e-14 piv 3.77983e-14
> Maximum: nopiv 4.83319e-14 piv 4.28309e-14
>
> So pivoting is slightly better, but the residual matrix LDL^T - A is even
> without pivoting so small that it's not clear whether it's worth the effort
> for random matrices. However, random matrices often work surprisingly well.
Random matrices are invertible, and pivoting strategies are typically
more useful when dealing with non invertible matrices.
Now I don't know if LDLt aims to support non-invertible matrices or
not. At least I don't see any reason why it wouldn't -- positive
indefinite matrices definitely do have a LDLt and even a LLt although,
contrary to the invertible case, the L in LLt is no longer unique.
> Incidentally, the documentation for setRandom() can be improved. It should
> mention what distribution is used and also something about setting the seed.
OK good point but this should rather be centralized in a dox page on
random numbers and matrices, because setRandom() wouldn't be the only
place where such documentation is needed.
To answer quickly your question:
for floating point numbers, uniform distribution on [-1,1]
for ints, uniform on {-10,...,+10}
You can see the seed with the standard library function srand(), since
our random numbers just call rand().
Cheers,
Benoit