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

**References**:**[eigen] Pivoting for LDLT***From:*Keir Mierle

**Re: [eigen] Pivoting for LDLT***From:*Jitse Niesen

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Pivoting for LDLT** - Next by Date:
**Re: [eigen] sdgfdf** - Previous by thread:
**Re: [eigen] Pivoting for LDLT** - Next by thread:
**Re: [eigen] Pivoting for LDLT**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |