RE: Using ROOT's root-finding algorithms

From: Amnon Harel <amnon.harel_at_cern.ch>
Date: Thu, 29 Mar 2012 11:20:12 +0000

Hi Lorenzo,

Thanks for your advice.

I learned some more on the subject and experimented a bit. The derivative based algorithms don't use the concept of a bracket, and are thus much less reliable. In particular, when they happen to encounter a very small derivative, they make huge jumps which are often counter productive.
I also tested derivative-based finders with my own transformation (also atan :-) ) code before getting your answer. Near the edges of the original problem, the slope of the transformed problem is very small. The fitters complained of derivative==0. I expect that machine precision is the real issue and that this approach is limited by it.

This more or less leaves Brent's root finding algorithm as the most robust tool. Unfortunately, ROOT's implementation is lacking. But that's the subject on another email.

 cheers,
 Amnon

---

From: Lorenzo Moneta
Sent: 27 March 2012 18:49
To: Amnon Harel
Cc: roottalk (Mailing list discussing all aspects of the ROOT system.) Subject: Re: [ROOT] Using ROOT's root-finding algorithms

Hi Amnon,

 The root-finding algorithms using derivatives need just an initial estimate of the root. They will not use a bisection, so they will find the root in the local region of the point. If you are sure your function is having a root in the interval [0,M] and the root is unique you can just use the middle as starting point. If the root instead sometimes might be outside the interval, then either use the Brent method or transform your variables in a -inf,+inf range using for example a sin transformation like: http://root.cern.ch/lxr/source/math/mathcore/src/MinimizerVariableTransformation.cxx#23

  Best Regards

 Lorenzo

On Mar 25, 2012, at 10:01 PM, Amnon Harel wrote:

> Dear ROOTers,
>
> I have some questions about how to best use ROOT's root-finding
> algorithms. I need to find the root of a 1D analytical function
> in a bound range [0, M]. The derivative of the function is available.
> As far as I can tell, in ROOT the algorithms that use the derivative
> do not accept a range. Does anyone know the rational for that?
>
> I need very fast performance, hence the use of the derivative.
> But perhaps Brent's method is so good that there's nothing
> to gain from a derivative?
>
> As a work-around, I can map (0, M) unto the entire real axis,
> and check the edges separately. This seems a generic trick, so
> I wonder if there's a reason, besides the obvious "no one got
> around to it", why this isn't available in ROOT?
>
> thanks,
> Amnon Harel
>
Received on Thu Mar 29 2012 - 13:20:20 CEST