or some such combination. I'll refer to the first parameter as the

*bootstrap traits*; the second is the interpolator already described in

a previous post. The third, and seemingly ungainly, parameter specifies a class which implements the bootstrapping algorithm. The parameter has a default value (the

IterativeBootstrap class, which I'll describe later) so you can happily forget about it most of the times; it is provided so that interested developers can replace the bootstrapping algorithm with another one, either provided by the library or of their own creation. If you're not familiar with its syntax, it's a template template parameter [1]. The repetition is not an error, as suspected by my spell checker as I write these lines; it means that the template parameter should, in turn, be an uninstantiated class template (in this case, one taking a single template argument) rather than a typename. (An uninstantiated template is something like

std::vector, as opposed to an instantiated one like

std::vector<double>. The second names a type; the first doesn't.)

Before declaring the class interface, we need another bit of template programming to determine the parent class of the curve. On the one hand, we inherit our term structure from the

LazyObject class; as described

here, this will enable the curve to re-bootstrap itself when needed. On the other hand, we want to inherit it from one of the interpolated curves described

here; depending on the choice of underlying data (discount, zero yields, or forward rates), we must select one of the available class templates and instantiate it with the chosen interpolator class. This is done by storing the class template in the bootstrap traits. Unluckily, C++ didn't allow template typedefs until recently (template aliases were introduced in the 2011 revision of the C++ standard). Therefore, the traits define an inner class template

curve which takes the interpolator as its template parameter and defines the instantiated parent class as a typedef; this can be seen in the definition of the

Discount traits, partially shown in listing 3.8.

Listing 3.8: Sketch of the Discount bootstrap traits.

struct Discount {
template <class Interpolator>
struct curve {
typedef InterpolatedDiscountCurve<Interpolator> type;
};
typedef BootstrapHelper<YieldTermStructure> helper;
// other static methods
}

The described machinery allows us to finally refer to the chosen class by using the expression

Traits::template curve<Interpolator>::type

that we can add to the list of parent classes. (For those unfamiliar with the dark corners of template syntax, the

template keyword in the expression is a hint for the compiler. When reading this expression, the compiler doesn't know what

Traits is and has no means to determine that

Traits::curve is a class template. Adding the keyword gives it the information, required for processing the rest of the expression correctly.) For the instantiation shown above as an example, with

Discount as bootstrap traits and

LogLinear as interpolator, the above works out as

Discount::curve<LogLinear>::type

which in turn corresponds—as desired—to

InterpolatedDiscountCurve<LogLinear>

as can be seen from the definition of the

Discount class.

We make a last short stop before we finally implement the curve; in order to avoid long template expressions, we define a few typedefs, namely,

base_curve,

this_curve, and

helper. The first one refers to the parent class; the second one refers to the very class we're declaring; and the third one extracts from the bootstrap traits the type of a helper class. This class will be described later in the example; for the time being, I'll just say that it provides the quoted value of an instrument, as well as the means to evaluate such instrument on the term structure being bootstrapped. The aim of the bootstrap will be to modify the curve until the two values coincide. Finally, two other typedefs (

traits_type and

interpolation_type) store the two corresponding template arguments so that they can be retrieved later.

The actual interface, at last. The constructors (of which only one is shown in the listing) take the arguments required for instantiating the parent interpolated curve, as well as a vector of helpers and the target accuracy for the bootstrap. Next, a number of inspectors (such as

times or

data) are defined, overriding the versions in the parent class; as we'll see, this allows them to ensure that the curve is fully built before returning the required data. The public interface is completed by the

update method.

The protected methods include

performCalculations, needed to implement the

LazyObject interface; and

discountImpl, which (like the public inspectors) overrides the parent-class version. The

Bootstrap class template is instantiated with the type of the curve being defined. Since it will need access to the internals of the curve, the resulting class is declared as a friend of the

PiecewiseYieldCurve class; the same is done for the

BootstrapError class, used in the bootstrap algorithm and described later. Finally, we store an instance of the bootstrap class, as well as the required curve accuracy and the helpers.

Listing 3.7 (continued)

template <class T, class I,
template <class> class B>
PiecewiseYieldCurve<T,I,B>::PiecewiseYieldCurve(
Natural settlementDays,
const Calendar& calendar,
const std::vector<shared_ptr<helper> >& instruments,
const DayCounter& dayCounter,
Real accuracy,
const I& interpolator)
: base_curve(settlementDays, calendar, dayCounter, i),
instruments_(instruments), accuracy_(accuracy) {
bootstrap_.setup(this);
}
template <class T, class I,
template <class> class B>
void PiecewiseYieldCurve<T,I,B>::update() {
base_curve::update();
LazyObject::update();
}
template <class T, class I,
template <class> class B>
void PiecewiseYieldCurve<T,I,B>::performCalculations() const {
bootstrap_.calculate();
}
template <class T, class I,
template <class> class B>
DiscountFactor PiecewiseYieldCurve<T,I,B>::discountImpl(Time t) const {
calculate();
return base_curve::discountImpl(t);
}

Let's now have a look at the implementation. The constructor holds no surprises: it passes the needed arguments to the base class and stores in this class the other ones. Finally, it passes the curve itself to the stored

Bootstrap instance and makes it perform some preliminary work—more on this later. The

update method is needed for disambiguation; we are inheriting from two classes (

LazyObject and

TermStructure) which both define their implementation of the method. The compiler justly refuses to second-guess us, so we have to explicitly call both parent implementations.

The

performCalculations simply delegates its work to the

Bootstrap instance. Lastly, a look at the

discountImpl method shows us why such method had to be overridden; before calling the parent-class implementation, it has to ensure that the data were bootstrapped by calling the

calculate method. This also holds for the other overridden inspectors, all following the same pattern. Instead, there's no need to override the

zeroYieldImpl and

forwardImpl methods, even if the curve inherits from

ZeroYieldStructure or

ForwardRateStructure; if you look back at listing 3.5

here, you'll see that those methods are only ever called by

discountImpl. Thus, overriding the latter is enough.

At this point, I need to describe the

BootstrapHelper class template; its interface is sketched in listing 3.9. For our curve, we'll instantiate it (as you can see in the

Discount traits shown earlier) as

BootstrapHelper<YieldTermStructure>; for convenience, the library provides an alias to this class called

RateHelper that can be used in place of the more verbose type name.

Listing 3.9: Interface of the BootstrapHelper class template.

template <class TS>
class BootstrapHelper : public Observer, public Observable {
public:
BootstrapHelper(const Handle<Quote>& quote);
virtual ~BootstrapHelper() {}
Real quoteError() const;
const Handle<Quote>& quote() const;
virtual Real impliedQuote() const = 0;
virtual void setTermStructure(TS*);
virtual Date latestDate() const;
virtual void update();
protected:
Handle<Quote> quote_;
TS* termStructure_;
Date latestDate_;
};

Each instance of this class—or rather, of derived classes; the class itself is an abstract one—will help bootstrapping a single node on the curve. The input datum for the node is the quoted value of an instrument; this is provided as a

Handle to a

Quote instance, since the value will change in time. For a yield curve, such instruments might be deposits or swaps, quoted as the corresponding market rates. For each kind of instrument, a derived class must be provided.

The functionality that is common to all helpers is implemented in the base class.

BootstrapHelper inherit from both

Observer and

Observable; the double role allows it to register with the market value and notify changes to the curve, signaling the need to perform a new bootstrap. Its constructor takes a

Handle<Quote> providing the input market value, stores it as a data member, and registers itself as an observer. Three methods deal with the underlying instrument value. The

quote method returns the handle containing the quoted value; the abstract

impliedValue method returns the value as calculated on the curve being bootstrapped; and the convenience method

quoteError returns the signed difference between the two values.

Two more methods are used for setting up the bootstrap algorithm. The

setTermStructure method links the helper with the curve being built. The

latestDate method returns the latest date for which curve data are required in order to calculate the implied value of the market datum; such date will be used as the coordinate of the node being bootstrapped. (The latest required date does not necessarily correspond to the maturity of the instrument. For instance, if the instrument were a constant-maturity swap, the curve should extend a few years beyond the swap maturity in order to forecast the rate paid by the last coupon.) The last method,

update, forwards notifications from the quote to the observers of the helper.

The library provides a few concrete helper classes inherited from

RateHelper. In the interest of brevity, allow me to do a little hand-waving here instead of showing you the actual code. Each of the helper classes implements the

impliedValue for a specific instrument and includes code for returning the proper latest date. For instance, the

DepositRateHelper class forecasts a quoted deposit rate by asking the curve being bootstrapped for the forward rate between its start and maturity dates; whereas the

SwapRateHelper class forecasts a swap rate by instantiating a

Swap object, pricing it on the curve, and implying its fair rate. In a multi-curve setting, it's also possible to use the bootstrapped curve for forecasting forward rates and an external curve for discounting. If you're interested, more details on this (and a discussion on what helpers to choose for a given curve) are available in Ametrano and Bianchetti [2].

We can finally dive into the bootstrap code. Listing 3.10 shows the interface of the

IterativeBootstrap class, which is provided by the library and used by default.

Listing 3.10: Sketch of the \texttt{IterativeBootstrap} class template.

template <class Curve>
class IterativeBootstrap {
typedef typename Curve::traits_type Traits;
typedef typename Curve::interpolator_type Interpolator;
public:
IterativeBootstrap();
void setup(Curve* ts);
void calculate() const;
private:
Curve* ts_;
};
template <class Curve>
void IterativeBootstrap<Curve>::calculate() const {
Size n = ts_->instruments_.size();
// sort rate helpers by maturity
// check that no two instruments have the same maturity
// check that no instrument has an invalid quote
for (Size i=0; i<n; ++i)
ts_->instruments_[i]->setTermStructure(
const_cast<Curve*>(ts_));
ts_->dates_ = std::vector<Date>(n+1);
// same for the other data vectors
ts_->dates_[0] = Traits::initialDate(ts_);
ts_->times_[0] = ts_->timeFromReference(ts_->dates_[0]);
ts_->data_[0] = Traits::initialValue(ts_);
for (Size i=0; i<n; ++i) {
ts_->dates_[i+1] = ts_->instruments_[i]->latestDate();
ts_->times_[i+1] =
ts_->timeFromReference(ts_->dates_[i+1]);
}
Brent solver;
for (Size iteration = 0; ; ++iteration) {
for (Size i=1; i<n+1; ++i) {
if (iteration == 0) {
// extend interpolation a point at a time
ts_->interpolation_ =
ts_->interpolator_.interpolate(
ts_->times_.begin(),
ts_->times_.begin()+i+1,
ts_->data_.begin());
ts_->interpolation_.update();
}
Rate guess;
// estimate guess by using the value at the previous iteration,
// by extrapolating, or by asking the traits
// bracket the solution
Real min = Traits::minValueAfter(i, ts_->data_);
Real max = Traits::maxValueAfter(i, ts_->data_);
BootstrapError<Curve> error(ts_, instrument, i);
ts_->data_[i] = solver.solve(error, ts_->accuracy_,
guess, min, max);
}
if (!Interpolator::global)
break; // no need for convergence loop
// check convergence and break if tolerance is reached; bail out
// if tolerance wasn't reached in the given number of iterations
}
}

For convenience, typedefs are defined to extract from the curve the traits and interpolator types. The constructor and the

setup method are not of particular interest. The first just initializes the contained term-structure pointer to a null one; the second stores the passed curve pointer, checks that we have enough helpers to bootstrap the curve, and registers the curve as an observer of each helper. The bootstrap algorithm is implemented by the

calculate method. In the version shown here, I'll gloss over a few details and corner cases; if you're interested, you can peruse the full code in the library.

First, all helpers are set the current term structure. This is done each time (rather than in the

setup method) to allow a set of helpers to be used with different curves. (Of course, the same helpers could not be passed safely to different curves in a multi-threaded environment since hey would compete for it. Then again, much of QuantLib is not thread-safe, so it's kind of a moot point.) Then, the data vectors are initialized. The date and value for the initial node are provided by the passed traits; for yield term structures, the initial date corresponds to the reference date of the curve. The initial value depends on the choice of the underlying data; it is 1 for discount factors and a dummy value (which will be overwritten during the bootstrap procedure) for zero or forward rates. The dates for the other nodes are the latest needed dates of the corresponding helpers; the times are obtained by using the available curve facilities.

At this point, we can instantiate the one-dimensional solver that we'll use at each node (more details on solvers in a future post) and start the actual bootstrap. The calculation is written as two nested loops; an inner one—the bootstrap proper—that walks over each node, and an outer one that repeats the process. Iterative bootstrap is needed when a non-local interpolation (such as cubic splines) is used. In this case, setting the value of a node modifies the whole curve, invalidating previous nodes; therefore, we must go over the nodes a number of times until convergence is reached.

As I mentioned, the inner loop walks over each node—starting, of course, from the one at the earliest date. During the first iteration (when

iteration == 0) the interpolation is extended a point at a time; later iterations use the full data range, so that the previous results are used as a starting point and refined. After each node is added, a one-dimensional root-finding algorithm is used to reproduce the corresponding market quote. For the first iteration, a guess for the solution can be provided by the bootstrap traits or by extrapolating the curve built so far; for further iteration, the previous result is used as the guess. The maximum and minimum value are provided by the traits, possibly based on the nodes already bootstrapped. For instance, the traits for bootstrapping zero or forward rates can prevent negative values by setting the minimum to a zero; the traits for discount factors can do the same by ensuring that the discounts are not increasing, i.e., by setting the maximum to the discount at the previous node.

The only missing ingredient for the root-finding algorithm is the function whose zero must be found. It is provided by the

BootstrapError class template (shown in listing 3.11), that adapts the helper's

quoteError calculation to a function-object interface. Its constructor takes the curve being built, the helper for the current node, and the node index, and stores them. Its

operator() makes instances of this class usable as functions; it takes a guess for the node value, modifies the curve data accordingly, and returns the quote error.

Listing 3.11: Interface of the

BootstrapError class template.

template <class Curve>
class BootstrapError {
typedef typename Curve::traits_type Traits;
public:
BootstrapError(
const Curve* curve,
const shared_ptr<typename Traits::helper>& helper,
Size segment);
Real operator()(Rate guess) const {
Traits::updateGuess(curve_->data_, guess, segment_);
curve_->interpolation_.update();
return helper_->quoteError();
}
private:
const Curve* curve_;
const shared_ptr<typename Traits::helper> helper_;
const Size segment_;
};

At this point, we're all set. The inner bootstrap loop creates a

BootstrapError instance and passes it to the solver, which returns the node value for which the error is zero—i.e., for which the implied quote equals (within accuracy) the market quote. The curve data are then updated to include the returned value, and the loop turns to the next node.

When all nodes are bootstrapped, the outer loop checks whether another iteration is necessary. For local interpolations, this is not the case and we can break out of the loop. For non-local ones, the obtained accuracy is checked (I'll spare you the details here) and iterations are added until convergence is reached.

This concludes the bootstrap; and, as I don't want to further test your patience, it also concludes the example. Sample code using the

PiecewiseYieldCurve class can be found in the QuantLib distribution, e.g., in the swap-valuation example.

[1] V. Simonis and R. Weiss,

. In

, Lecture Notes in Computer Science 2244, Springer Berlin/Heidelberg, 2001.

[2] F. Ametrano and M. Bianchetti,