Re: [eigen] Re: LU precision tuning |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] Re: LU precision tuning*From*: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>*Date*: Mon, 11 May 2009 01:16:56 +0200*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=iNRIglAf8qvnHgea7WEL4zxK4mLNa6Dk/GdG8Hu8vQI=; b=K9i5r/UT9d6DAybdeYvBEPY+AP+GaKXS01AXXj+/wr3e+cTiKNkJQnYUPr81+Lgx4m xmccgJjKyijnTfAx7KdxCXeJCQHh+waLJWyOCFKvIeX3+wnYze5y4E1eEhNDrCv6/EiC gG6ibZgRcb/PjWuDqoZgv+KPyni4i3Q3LpJkA=*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=NypQlqALucyhNkiZe8EiG9+PD27YHMkJQDmdbdPEjPap98Sn4plH0CtiuQuTsTy1SS 5+AZidrX4NxfLzBv9v0NXQSJcvxvkf042xR3NGYPV/XnCPaZ38hlS7ly6bNcDHM/iqn8 IKcdkuhiyGglEEEpvypfhJCdNaLlltB3CarT8=

Bah. I spend an hour trying to get something significant, but not much success. I don't want to encourage you to do more experiments either as I think that we won't get much farther than where your last table takes us: I've been thinking a bit more about all that: matrices of floating-point numbers don't really have a well-defined rank, since the "rank" function is not continuous. This means that it's inevitable that any rank() method doesn't always return what we expect. The main conclusion that I draw from your last table is that our formula "epsilon*size" is pretty good in general; following your last table, one may be tempted to take something slightly coarser, but then by taking a nastier random matrix with near-zero nonzero singular values, one would be led to take something arbitrarily coarse. So instead, the conclusion i draw from your table is that we won't do any better than "epsilon*size" as a compromise (between rank accuracy and solving accuracy) in general, but we should let the user override that if he knows something we don't (that is: the condition number of the nonzero singular values). I'll commit that tomorrow, just a slight modification of your patch to default to "epsilon*size". Also, there's a problem in your create...() function for rectangular sizes: it's d that should be rectangular, not a; the matrix m you create is always square as a product of 3 square matrices. I'll take care of that. Benoit 2009/5/10 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>: > Further thought: > since it's looking like exact rank computation is beyond the scope of > LU and QR, it might be that the really interesting thing to measure is > rather the "average error" or "standard deviation" or some other > statistical quantity. > > Benoit > > 2009/5/10 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>: >> Hi, >> >> Thanks a lot for your results. >> >> It isn't looking well for guaranteed exact rank determination. >> Especially considering that your random matrices are still nice in the >> sense that your singular values (the diagonal matrix used to construct >> them) is 1,...,1,0,....,0 and it would be even much worse if one of >> the nonzero values here were small. >> >> We can't increase the value of 'precision' forever until we reach >> exact rank determination, as that decreases the accuracy of solving. >> >> So, after your results, I propose that we give up trying to guarantee >> exact rank determination with LU and QR: that probably wasn't very >> realistic and the right tool to approach that goal is rather the SVD. >> We can say that in the docs. >> >> If we do that, then the current formula "machine_epsilon * size" seems >> like a good compromise. We can also allow the user to pass a >> "precision" optional parameter in LU and QR, in other words just apply >> your patch, to allow the user to choose his own compromise. >> >> Cheers, >> Benoit >> >> 2009/5/10 Hauke Heibel <hauke.heibel@xxxxxxxxxxxxxx>: >>> Some more results including the related patch and code - this time the >>> tests include the QR decomposition. >>> >>> After (hopefully) fixing (with Benoit's help) the creation of matrices >>> having a specific rank, I reran the tests. This time with increased >>> 'repeat' variable - I set it to 200. Due to the long time it takes, I >>> stopped at a matrix size of 512. >>> >>> The results were not only run for LU but also QR and they indicate >>> that for LU our bound might be a bit too tight - especially for bigger >>> matrices. For QR on the other hand it still looks too noisy to infer >>> any formula. >>> >>> The 'ups' from the log-file denotes a complete failure, i.e. for all >>> tested precisions in the range of [eps; eps*2^19] at least one out of >>> 200 tests failed. >>> >>> - Hauke >>> >> >

**Follow-Ups**:**Re: [eigen] Re: LU precision tuning***From:*Hauke Heibel

**References**:**[eigen] LU precision tuning***From:*Benoit Jacob

**[eigen] Re: LU precision tuning***From:*Benoit Jacob

**[eigen] Re: LU precision tuning***From:*Benoit Jacob

**[eigen] Re: LU precision tuning***From:*Benoit Jacob

**[eigen] Re: LU precision tuning***From:*Benoit Jacob

**Re: [eigen] Re: LU precision tuning***From:*Hauke Heibel

**Re: [eigen] Re: LU precision tuning***From:*Benoit Jacob

**Re: [eigen] Re: LU precision tuning***From:*Hauke Heibel

**Re: [eigen] Re: LU precision tuning***From:*Benoit Jacob

**Re: [eigen] Re: LU precision tuning***From:*Benoit Jacob

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Re: LU precision tuning** - Next by Date:
**Re: [eigen] Diagonal matrices diff** - Previous by thread:
**Re: [eigen] Re: LU precision tuning** - Next by thread:
**Re: [eigen] Re: LU precision tuning**

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