Optimization of Brent Solver

Posted by Sebastian Poloczek on Jul 26, 2012; 2:30pm
URL: http://quantlib.414.s1.nabble.com/Optimization-of-Brent-Solver-tp8948.html

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