commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <Luc.Maison...@free.fr>
Subject Re: [jira] [Created] (MATH-635) High order Brent-like bracketing solver
Date Fri, 29 Jul 2011 09:52:44 GMT
Hello,

Le 29/07/2011 11:15, Luc Maisonobe (JIRA) a écrit :
> High order Brent-like bracketing solver
> ---------------------------------------
>
>                   Key: MATH-635
>                   URL: https://issues.apache.org/jira/browse/MATH-635
>               Project: Commons Math
>            Issue Type: New Feature
>              Reporter: Luc Maisonobe
>              Assignee: Luc Maisonobe
>               Fix For: 3.0
>
>
> The new bracketing solvers greatly improve usage. Unfortunately, for now there are only
secant-based bracketing solvers available, and a wrapper which basically ends by adding a
few secant steps to regular non-bracketing solvers.
>
> Changing the Brent solver to provide bracket selection on the final result would depart
from the standard algorithm, which is a wrong move (see MATH-599 for a similar case recently
resolved).
> It would be nice to set up another solver in the same spirit as Brent (i.e. using inverse
polynomial interpolation when possible and falling back to dichotomy) while retaining bracketing.
A nice and simple improvement is also to use higher order inverse polynomial interpolation
by retaining several previous points. This allows to build a solver that have an higher order
than Newton for example but still only needs function values and no derivatives at all.

As you have probably guessed, this solver is already developed. I have 
played with this idea for a while and implemented it last week end 
during two long train trips. It works pretty well.

The idea is really simple: start with a two or three points array 
containing min, max and if present startValue to build the inverse 
interpolation polynomial exactly in the same spirit as Brent (inverse 
interpolation is *really* a fabulous trick). Then as new points are 
computed trying to find the root, they are added to the array and the 
order of the inverse interpolation increases (quadratic with 3 points, 
cubic with four points ...). Strangely enough, I did not find any 
reference on such a method, but I still think it should be well known 
(Brent method is from the 60's). So if anybody can point me to a 
reference paper and analysis, I would be glad to adapt my home grown 
method to something more standard. If there are no paper, I probably can 
write a small analysis on it and publish it on my site but I doubt it 
would be interesting.

As I was testing the implementation, I noticed we had no Dfp-based 
solver, so I converted (it was a 10 minutes work) the solver to have
a Dfp-based one. I have open another issue for that (MATH-636). It seems 
to work well. However, I don't know were I should put this. It would be 
probably overkill to set a complete set of interfaces, abstract classes 
and implementations in the analysis.solver packe for Dfp functions. I 
think about setting simply a UnivariateDfpFunction interface and only 
one BracketingNthOrderBrentSolverDFP class, both in the dfp package. 
What do you think about it ?

Another thing I want to ask fellow developers it to try to stress-test 
these implementation (I'll commit them probably later today).

thanks,
Luc

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message