LAPACK Archives

[Lapack] [lapackers] Re: lapack bug in divide-and-conquer: is anybody li

Jim,

I have to clarify that the code does not do strict bisection. It uses bisection 
as the fall back when the computed approximation somehow gets out of the 
interval that the approximation should be in. Then one step of bisection is 
taken and then it goes back to the usual Newton-like method again (because 
that's faster). The interval is updated every step and thus shrinking. Xlasd4 
was handled similarly.

Setting MAXIT=20 was too aggressive by my side as we know now. MAXIT=64 may be 
too conservative. Perhaps we should set MAXIT=40. If that breaks in the future, 
I'd really like to revisit the code. But if we'd like to play it safe, your 
suggested 64 would be the best bet.

best, -rencang

PS. Apparently my email won't go to lapackers and beboppers 

________________________________________
From: James Demmel [demmel@Domain.Removed]
Sent: Monday, November 22, 2010 1:30 PM
To: lapackers@Domain.Removed; julie langou
Cc: Li, Ren-cang; James Demmel; lapack@Domain.Removed; beboppers; lapackers
Subject: Re: [lapackers] Re: [Lapack] lapack bug in divide-and-conquer: is 
anybody listening

Ren-Cang, can we put a hard limit on the number of iterations,
the worst case in case you switch to bisection? In a 64-bit
floating point format, you can arrange bisection to take at most
64 steps, but of course the "bisection" may work a bit differently,
the first 11 steps to get the exponent bits if necessary (eg
if the interval contains 0), and the next 52 as usual to get the
mantissa bits (I'm not sure we do this in slaebz either...).
Jim

julie langou wrote:
Dear Rencang,
Indeed the user needed only 23 iterations in his case.
See http://icl.cs.utk.edu/lapack-forum/viewtopic.php?f=2&t=529
<http://icl.cs.utk.edu/lapack-forum/viewtopic.php?f=2&t=529>
Regards,
Julie
On Nov 20, 2010, at 11:03 AM, Li, Ren-cang wrote:

Jim,

Each iteration operates within a shrinking interval which contains
the desired root, and the bisection is called whenever the iteration
goes out of the interval; so the bisection is the fall back (I just
double checked). 200 is extreme, but I think it should never get that
far, otherwise I would be really worried. It would be helpful if
someone could tell me what is the exact number of iterations needed
to fix that bug.

best, -rencang

________________________________________
From: James Demmel [demmel@Domain.Removed]
Sent: Saturday, November 20, 2010 10:00 AM
To: julie langou
Cc: lapack@Domain.Removed <mailto:lapack@Domain.Removed>; lapackers;
beboppers; Li, Ren-cang
Subject: Re: [Lapack] lapack bug in divide-and-conquer: is anybody
listening

And sorry for also not getting to this sooner. When you say that the
convergence bug in divide-and-conquer was fixed by raising MAXIT
from 40 to 200 in xlaed4 (written by Ren-Cang), then that makes me
think that some flavor of bisection would be a better fall-back when
convergence fails (since the maximum number of iterations could be
more like the number of bits in the floating point word, so 32 or 64).
This is very intricate code (and asking the to-be-hired programmer to fix
it would likely require a very long learning curve) so let me ask
Ren-Cang
if he has any opinions.

Thanks,
Jim

julie langou wrote:
Evan,
Sorry for not getting back to you earlier.
We indeed corrected the bug you found, thank you for the patch. It is
released in LAPACK 3.3.0 (released this week).
See http://www.netlib.org/lapack/bugfixedin33.txt.
This bug was labelled bug0064.
If you could confirm that this issue is fixed, I will add a post on
the forum to let the users know.
Regards,
Julie

On Nov 18, 2010, at 8:25 AM, Evan Drumwright wrote:

Hi,

Please allow me to say how much I use and appreciate lapack.  It
makes my research *much* easier and I would be stuck without it.


... which is why the following problem is so disconcerting.  I am
experiencing a bug related to least squares solution via singular
value decomposition that at least one other person has experienced
and have gotten no response on the lapack user's forum from the
lapack maintainers.

Please see:

http://icl.cs.utk.edu/lapack-forum/viewtopic.php?f=2&t=529
<http://icl.cs.utk.edu/lapack-forum/viewtopic.php?f=2&t=529>
<http://icl.cs.utk.edu/lapack-forum/viewtopic.php?f=2&t=529
<http://icl.cs.utk.edu/lapack-forum/viewtopic.php?f=2&t=529>>

for a description of the bug, conditions to reproduce it, and a fix.
I would greatly appreciate it if this fix made its way into lapack!

Thanks and regards,
Evan Drumwright

_______________________________________________
Lapack mailing list
Lapack@Domain.Removed <mailto:Lapack@Domain.Removed> 
<mailto:Lapack@Domain.Removed>
http://lists.eecs.utk.edu/mailman/listinfo/lapack

**********************************************
Julie Langou; Research Associate in Computer Science
Innovative Computing Laboratory;
University of Tennessee from Denver, Colorado ;-)
julie@Domain.Removed <mailto:julie@Domain.Removed>
<mailto:julie@Domain.Removed>; http://www.cs.utk.edu/~julie/
<http://www.cs.utk.edu/%7Ejulie/>
<http://www.cs.utk.edu/%7Ejulie/>







------------------------------------------------------------------------

_______________________________________________
Lapack mailing list
Lapack@Domain.Removed <mailto:Lapack@Domain.Removed>
http://lists.eecs.utk.edu/mailman/listinfo/lapack

_______________________________________________
Lapack mailing list
Lapack@Domain.Removed <mailto:Lapack@Domain.Removed>
http://lists.eecs.utk.edu/mailman/listinfo/lapack

**********************************************
Julie Langou; Research Associate in Computer Science
Innovative Computing Laboratory;
University of Tennessee from Denver, Colorado ;-)
julie@Domain.Removed
<mailto:julie@Domain.Removed>; http://www.cs.utk.edu/~julie/
<http://www.cs.utk.edu/%7Ejulie/>








<Prev in Thread] Current Thread [Next in Thread>


For additional information you may use the LAPACK/ScaLAPACK Forum.
Or one of the mailing lists, or