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 Newtonlike 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, Rencang; James Demmel; lapack@Domain.Removed; beboppers; lapackers
Subject: Re: [lapackers] Re: [Lapack] lapack bug in divideandconquer: is
anybody listening
RenCang, can we put a hard limit on the number of iterations,
the worst case in case you switch to bisection? In a 64bit
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/lapackforum/viewtopic.php?f=2&t=529
<http://icl.cs.utk.edu/lapackforum/viewtopic.php?f=2&t=529>
Regards,
Julie
On Nov 20, 2010, at 11:03 AM, Li, Rencang 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, Rencang
Subject: Re: [Lapack] lapack bug in divideandconquer: is anybody
listening
And sorry for also not getting to this sooner. When you say that the
convergence bug in divideandconquer was fixed by raising MAXIT
from 40 to 200 in xlaed4 (written by RenCang), then that makes me
think that some flavor of bisection would be a better fallback 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 tobehired programmer to fix
it would likely require a very long learning curve) so let me ask
RenCang
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/lapackforum/viewtopic.php?f=2&t=529
<http://icl.cs.utk.edu/lapackforum/viewtopic.php?f=2&t=529>
<http://icl.cs.utk.edu/lapackforum/viewtopic.php?f=2&t=529
<http://icl.cs.utk.edu/lapackforum/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/>
