[
https://issues.apache.org/jira/browse/MATH-156?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Luc Maisonobe resolved MATH-156.
--------------------------------
Resolution: Fixed
Fix Version/s: (was: 1.2)
Nightly Builds
fixed in SVN revision 536283 (checked in 2007-05-08)
> Brent solver is non-optimal, because it doesn't use the user's guess.
> ---------------------------------------------------------------------
>
> Key: MATH-156
> URL: https://issues.apache.org/jira/browse/MATH-156
> Project: Commons Math
> Issue Type: Improvement
> Reporter: Tyler Ward
> Assigned To: Luc Maisonobe
> Fix For: Nightly Builds
>
>
> Hi guys, I noticed that your brent solver isn't using the initial guess given
> by the user. This can often radically improve the performance of the solver.
> In my tests, it improved it by roughly 30% or more, with a decent guess.
> Basically, we should try the guess first. If that's close enough, rreturn it.
> Otherwise, try one of the end points. If that's close enough, return it. Then
> if that brackets, go into the main loop. If that doesn't bracket, then we
> instead try the other endpoint. If that's close enough, return it. If that
> doesn't bracket, throw an exception. If it does bracket, go into the main
> loop with all three trial points available, allowing the quadratic
> interpolation to be used immediately.
> Worst case scenario, the initial guess doesn't bracket. In that case it is
> better than the default algorithm only if the user's initial guess is better
> than linear interpolation, which I imagine it almost always would be. If the
> user can't guess better than linear interpolation, presumably they wouldn't
> provide a guess at all, and then nothing would change.
> It's a small addition, less than 100 lines of code. I can't send it in due to
> legal at work, but from the above ideas, you should be able to put it in
> easily. One caveat. You may need to slightly modify the baisic solve(double,
> double) method to linearly interpolate a good beginning point and then break
> out a six double (solve(x0, y0, x1, y1, x2, y2)) method that both solve(min,
> max) and solve(min, max, initial) can use. If you don't do this, then
> solve(min, max) will bisect on its first iteration rather than intepolating,
> which could cost performance. If you do break it out like so, then this will
> always perform better than the current implementation.
> As a good case study, here's our situation from work.
> We are trying to compute a root, we know it falls in a VERY large interval
> (in this case -1.0 to 1.0), but more than 99% of the time it will be between
> (say) 1.04 and 1.07. We can guess with stunning accuracy, at least 90% of the
> time we can come to within 10^-4 for very little cost (a very nice cubic
> approximation of the more complicated function), but we really need it to
> within 10^-8 or better. In addition, that 1% of the time, it can fall in very
> strange areas (0.9, or -0.3 or so), and our guess isn't very good when that
> happens. So we can't tighten down the interval, because that would cause
> spurious errors, and at the same time your linear interpolation isn't going
> to be very good at all. It easily takes you 3 or 4 steps to get as close as
> our first guess. Using the first guess in this manner would cut the steps to
> convergence from about 8-10 to about 3-5. A speed up of around 100%, with no
> loss in accuracy.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
