|Re: [eigen] Re: LU precision tuning|
[ Thread 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
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.
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.
> 2009/5/10 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>:
>> 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.
>> 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