Optimization of Brent Solver

[Sebastian Poloczek]

Hi,

it seems that in the current implementation of Brent solver the commited guess value is not used at all. The method Solver1D::solve(const F& f, Real accuracy, Real guess, Real xMin, Real xMax) does set root_ = guess. The next command line calls the solver ( return this->impl().solveImpl(f, accuracy); ).

In case of the Brent solver the function Brent::solveImpl(const F& f, eal xAccuracy) is called. At the beginning of this function root_ is reset to xMax_: root_ = xMax_ and the guess value is lost.

Especially Brent Solver is used in the iterativebootstrap class. In case of the "discounting version" the guess for the next discount factor is calculated by extrapolating the already bootstrapped curve. This is simple, yet quite efficient. In the current Brent solver implementation this guessed value is lost. To improve this the following codechange seems to work:  

      // guess is ignored in current implementation... this should improve the solver performance
      froot = f(root_);
      if (froot * fxMin_ < 0){
        xMax_ = xMin_;
        fxMax_ = fxMin_;
      }
      else {
        xMin_ = xMax_;
        fxMin_ = fxMax_;
      }
      e=d=root_- xMax_;

   instead of the existing lines:
   root_ = xMax_;
   froot = fxMax_;

In the case of yield curve bootstrapping I get a speed benefit of about 45% ( 100000 bootstrap calculations of the same curve using both implementations). Calculated discount factors are (of course) identical in both cases.

Regards
Sebastian
   

[Luigi Ballabio]

Hi Sebastian,
    I applied the patch to the repository.  Thanks!

Luigi

On Thu, Jul 26, 2012 at 4:30 PM, Sebastian Poloczek
<[hidden email]> wrote:

>
> Hi,
>
> it seems that in the current implementation of Brent solver the commited
> guess value is not used at all. The method Solver1D::solve(const F& f, Real
> accuracy, Real guess, Real xMin, Real xMax) does set root_ = guess. The next
> command line calls the solver ( return this->impl().solveImpl(f, accuracy);
> ).
>
> In case of the Brent solver the function Brent::solveImpl(const F& f, eal
> xAccuracy) is called. At the beginning of this function root_ is reset to
> xMax_: root_ = xMax_ and the guess value is lost.
>
> Especially Brent Solver is used in the iterativebootstrap class. In case of
> the "discounting version" the guess for the next discount factor is
> calculated by extrapolating the already bootstrapped curve. This is simple,
> yet quite efficient. In the current Brent solver implementation this guessed
> value is lost. To improve this the following codechange seems to work:
>
>       // guess is ignored in current implementation... this should improve
> the solver performance
>       froot = f(root_);
>       if (froot * fxMin_ < 0){
>              xMax_ = xMin_;
>         fxMax_ = fxMin_;
>       }
>       else {
>         xMin_ = xMax_;
>         fxMin_ = fxMax_;
>       }
>       e=d=root_- xMax_;
>
>    instead of the existing lines:
>    root_ = xMax_;
>    froot = fxMax_;
>
> In the case of yield curve bootstrapping I get a speed benefit of about 45%
> ( 100000 bootstrap calculations of the same curve using both
> implementations). Calculated discount factors are (of course) identical in
> both cases.
>
> Regards
> Sebastian
>
> --
> View this message in context: http://old.nabble.com/Optimization-of-Brent-Solver-tp34215920p34215920.html
> Sent from the quantlib-dev mailing list archive at Nabble.com.
>
>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> QuantLib-dev mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/quantlib-dev

------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev