Re: [eigen] Re: LU precision tuning

[Benoit Jacob <jacob.benoit.1@xxxxxxxxx>]

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
>>>
>>
>