C(omp)++ | A Portal for the Computational Finance Community

An Introduction to the Boost Library

by Daniel Duffy

C++ continues to evolve and already STL is part of the official standard. I would like to discuss some new developments that are taking place and in particular we give an overview of the boost library (www.boost.org), a suite of useful C++ libraries containing functionality in the form of template classes:

• Multiarray: defines a generic interface to multidimensional containers
• Random numbers: contains a number of classes for generators and statistical distributions
• Property map: classes that embody key-value pairs and definition of the corresponding access (for example read and write)
• Smart pointers: objects that store pointers to dynamically allocated (heap) objects
• Graph library: a C++ library implementing graphs, networks and related graph algorithms

The authors (as well as many other software developers) have developed a subset of the functionality contained in these libraries. For example, in Duffy 2004 and Duffy 2006 we have implemented a template Property Map class with properties similar to that in boost; furthermore, we have created classes for two-dimensional matrices and three-dimensional tensors using nested STL classes. If we were to build such classes again, we would choose to use the boost library as underlying substrate.
We give a short description of the functionality in the above libraries. At this stage we avoid dealing with the C++ details on how to use these libraries in an application (they will be discussed later). We summarise each library as a list of features:

   

Multiarray
    Array classes for n-dimensional data
    Accessing the elements of array using () and [] operators
    Creating views of an array having the same or less dimensions
    Determining storage ordering of data (C-style, Fortran-style or user-defined)
    Defining or changing array index (zero is default)
    Changing an array’s shape
    Resizing an array (increasing or decreasing the extent of a dimension in an array)

   

Random Numbers
    Linear congruential generators
    Mersenne Twister generator
    Lagged Fibonacci generators
    Classes for continuous statistical distributions
    Classes for discrete statistical distributions

   

Property Maps
    Key-value pair concept
    Readable and writable data
    Support for built-in C++ data types
    Applicability to Boost Graph Library (BGL)

   

Smart Pointers
    Sole ownership to single objects and arrays
    Shared ownership of objects and arrays
    Shared ownership of objects with embedded reference counting

The gradual introduction of these features in applications will promote the reliability, maintainability and efficiency of your software. We shall see next how to use these libraries and to apply them to the Monte Carlo method and other applications in finance.

In the next blogs we shall give some examples in C++ and applications to the Monte Carlo method.

Financial Applications of Excel Add-In Development in C/C++ by Steve Dalton

Since authors are, first and foremost, consumers of books, I wanted this edition to be worth buying again, as there’s nothing worse than a second edition that isn’t. However, large sections of the book are very much like the first, and so I’m very happy to be able to explain here what almost two years’ effort has been all about.

Holes have been filled and areas augmented, many of these arising from questions I have received since publication.

The example code class, cpp_xloper, that encapsulates Excel’s xloper data type, now wraps the call-backs Excel4 and Excel4v, allowing for faster, clearer and safer coding. There’s a skeleton XLL project containing a shell worksheet function and a shell command, providing a simple starting point.

There are new financial applications, including SABR and simple CMS derivatives. As before, these are there simply to illustrate how to encapsulate real problems with fast and flexible interfaces.

Microsoft Excel 2007 is the most important release, for XLL developers, since Excel 97. Much of the book’s new material explores the opportunities and challenges that this raises. Two key new features are multi-threaded workbook recalculation and a grid that is over 1,000 times larger than that of Excel 2003. Microsoft have written a new Excel C API and SDK which provides new data types that support the larger grids, and for the first time, long Unicode strings. Thread-safe XLL worksheet functions can be registered as such, enabling Excel 2007 to call them concurrently on multiple threads. This not only leads to faster recalculation on multi-processor and -core machines, but also XLLs that can harness highly-parallel servers. The application to Monte Carlo simulation is obvious.

Programming in a multi-threaded environment will be a new challenge for many XLL developers. Thread-safe programming techniques are carefully explained in an XLL context: where, when and how to use them.

I am very grateful to those who bought the first book and provided feedback. The second edition is a much better book in part because of them. I hope those who buy it will get as much out as I have tried to put in.

I’d be happy to respond to any questions or feedback you might have.

Steve

To pre-order: Financial Applications using Excel Add-in Development in C/C++, 2nd Edition

Publishing July 13th, 2007

C++ Parallel Processing in Computational Finance, Part I: An Overview of OpenMP www.openmp.org

This blog is the first in a series of three blogs on the application of parallel programming techniques to Computational Finance with special attention being paid to Monte Carlo and PDE techniques. The current blog is meant as an overview of OpenMP at 30,000 feet.

OpenMP is a software product consisting of a collection of compiler directives (called pragmas), library functions and environment variables that developers can use to specify shared-memory parallelism in C. By shared memory we mean that all threads share a single address space and they communicate with each other by writing and reading shared variables. The OpenMP Application Programming Interface (API) is portable between various shared memory models. It has been tailored in such a way to support programs than run in both parallel and sequential modes. It is especially useful for large array-based applications. The main features are:

• Support for parallelization of loops and iterations

• Work-sharing constructs and the construction or parallel regions

• Synchronisation constructs

• Sharing and privatization of data

We shall discuss how to realize the above features in OpenMP in the next blog.

Many engineering, scientific and computational finance applications are expressed in the form of iterative constructs. In these cases the code consists of various kinds of loops. In general, loops are needed when we need to navigate in (hierarchical) data structures such and vectors, matrices, trees and graphs. Improving the performance of applications that rely heavily on loop constructs is a high priority. Given that many developers will choose to port their serial programs to the equivalent parallel ones using OpenMP we now discuss the forces to be reckoned with when we port loop-based code written for serial machines to parallelized loop code. There are a number of forces to examine that are related to the correctness and efficiency of the parallel code:

. Sequential equivalence: a given program should produce the same results when executed with one thread or with more than one thread. We use a series of transformations that we apply on the loops in order to achieve this end. These are called semantically neutral transformations if they leave the semantics of the program unchanged. A point to note is that due to round-off errors the results from a serial loop may be different from those in the equivalent parallel loop. For example, adding numbers in a loop will give different answers depending on the order in which they are added, for example if we add the numbers serially or in ascending order. This may be unacceptable and we should then decide not to parallelise the loop.

. Incremental parallelism: we parallelise a program by examining one loop at a time, for example. We apply a sequence of incremental transformations and we test the sequential equivalence after each increment. In this way we can be assured of correctness on the one hand and we can measure the performance improvement on the other hand.

. Memory utilization: In order to achieve good performance it is important to note that the way data is accessed (for example, using indexing operators or by dereferencing) is consistent with the memory model of the operating system.

 

Any comments or questions, I’d be happy to answer them.

Daniel

 

"Free Seminar Evening – Software Frameworks in C++ and C# for Applications in Computational Finance" by Daniel Duffy

Speaker: Daniel J. Duffy, Datasim

Date and Time: Tuesday 26 June 2007, 18.30 to 20.30

Venue: City of London

Registration: contact Ilona Hooft Graafland

In this seminar we discuss how modern software design techniques are used to create applications in Computational Finance using C++ and C# as the implementation languages. We elaborate on the object-oriented and generic programming features that we employ to create robust and maintainable software systems for a range of derivatives applications such as equities and interest rates. In particular, we concentrate on PDE/FDM and Monte Carlo methods.

Some of the topics to be considered are:

• Designing architectural Frameworks for financial applications

• Combing the object-oriented and generic programming models

• Developing applications for Monte Carlo and PDE

• Choosing between C++ and C#: creating interoperable applications

Who should attend:

• Quants and quant developers

• Managers who wish to gain insight into the software development process in Computational Finance 

Program:

18.00 – 18.30 Refreshments and Registration

18.30 – 19.30 C++ and C# for Computational Finance

19.30 – 1945 short break/refreshments

19.45 – 20.30 Option Pricing with PDE and Monte Carlo

20.30 end of seminar

About the Speaker: view Daniel's profile

Daniel Duffy: C++ Frameworks for Monte Carlo, Part II - The Top-level Architecture

In the last blog I discussed the design of the SDE and FDM components that allows us to create paths for the underlying assets. In this blog I would like to describe the other components in the framework as well as alluding to some of the POSA and GOF design patterns that help to promote maintainability, suitability and efficiency of the resulting C++ implementation.

The software system consists of three major subsystems/components. Each component has a well-defined responsibility and it provides standardized interfaces to other components that require services from it:

.  SDE/FDM; simulates paths of the underlying asset and in particular provides simulated asset prices at the expiry date, for example;
.  Instrument/Payoff: models the different kinds of payoff and related instruments. In particular, this component is able to calculate prices and sensitivities. This component encapsulates the Monte Carlo engine for a single instrument;
.  Client Components: customizable and extendible functionality for a range of applications. For example, we can produce statistical reports, VAR calculations and multi-asset applications.

We model each of these components using the Mediator pattern because this ensures loose coupling. Each participant in this pattern is modeled using a Layers pattern because this allows us to separate the UI aspects of the problem from the application logic. At the code level, we use Visitor because it allows developers to extend the functionality of the framework in a non-intrusive way.

One important remark: we combine the OO way with generic programming. In general we have used a number of template classes in the framework and the class hierarchies are at most two to three levels deep. A combination of the inheritance and delegation mechanisms seems like a good choice.

In the next blog we shall discuss some more detailed design issues, for example using Property Sets for modeling payoffs.

Any comments?

Daniel

Joerg: LAS VEGAS...as we may call the application of Monte Carlo methods to price American / Bermudan options.

In this blog we look into Las Vegas methods. American / Bermudan options exhibit early exercise opportunities. Thus the option holder does not have to wait until maturity to execute his right to exercise the option. The question arising here is the time point when it is optimal to exercise. The difference between the two types is that an American option can be exercised at any time until maturity whereas a Bermudan option has specified dates at which exercise is possible. The American option can be seen as a limiting case of a Bermudan. We actually only consider Bermudan types in Monte-Carlo.

One of the most well known and widely applied methods is the Longstaff-Schwarz regression method. Here an early exercise policy is determined using linear regression.

The price of an American / Bermudan option is given by

(1)

   

where U denotes the discounted expected payoff at time

Since in the above mentioned method we derive one of many exercise policies and formula (1) states that to actually price the contract we need the optimal policy we only compute a lower bound on the price.

Let us briefly review the method. We denote bythe possible exercise dates.

Firstly, you have to generate M₁ paths corresponding to your underlying dynamic. Second you apply regression on the possible exercise dates as follows:
Let denote the discounted price at time as above and denote by regression functions, e.g. polynomials. We suggest to compute

(2)

This task essentially involves matrix operations as inversion and multiplication. Working backwards through the exercise dates leads to regression coefficients at those points.

Now, run another simulation to generate M₂ paths. Together with the results in the first phase, the regression phase, we can determine the continuation value    using

This could be seen as the expected price under the assumption not to exercise immediately. An exercise policy for each path can be derived by comparing the continuation value CV to the value computed due to the given payoff at current time point. This phase we call the pricing phase. The obtained result determines a vector of size M₂ with values in the set . The values determine the exercise policy corresponding to the paths. The symbol suggests that we do not exercise until maturity and the option expires worthless. Now computing the resulting values with respect to the exercise policy and averaging gives the desired value of the American / Bermudan option.

 

Of course this method incorporates errors such as

• Estimation of continuation value
• In general smooth parameterisation functions used in the regression phase
• Too few paths might be considered
• Foresight bias

In future blogs we will explore some more details of the Longstaff-Schwarz method as well as review some other methods to price American / Bermudan options. Until then, I would be very pleased if anybody would like to share experiences on the pricing of early exercise features using Monte-Carlo, e.g. what is your favourite method? In which context do you apply such methods? Fixed-Income? Equity?

Joerg

 

Daniel: Designing Monte Carlo Frameworks, Part 1 - Generating Sample Paths

This is the first in a series of three blogs in which we discuss the application of system and design patterns to the development of customizable C++ code for Monte Carlo applications. We focus on the issue of sample path generation (as discussed in the book by Paul Glasserman, for example) and to this end, we have designed a system that approximates the solution of n-factor stochastic differential equations (SDEs) using numerical methods, for example Finite Difference Methods (FDM).  The system consists of a set of loosely coupled components. Each component has one major responsibility and it offers services to other components in the form of standardized and unambiguous interface functions as shown in the figure that is documented as a component diagram in UML 2.0, the de facto standard in object-oriented and component analysis. In this case we use this ball-and-socket notation to externalize and specify the contracts between the different components in the system:

. SDE: models n-factor stochastic differential equations. We support GBM and jump-diffusion models based on Levy processes

. RNG: the random number component that generates pseudo-random numbers. It implements Mersenne-Twister, Box Muller and other generators

. FDM Solver: this is the component that implements a range of finite difference solvers such as Euler, Milstein, Predictor Corrector and others. It requires the services of a mesher that is responsible for the generation of suitable mesh data.

. Solver: this mediator integrates the other components. It produces multi-dimensional data for use by other systems, for example when we need to model payoffs in n-factor options models.

Having defined the components and their interfaces we can now concentrate on designing them. To this end, we use a combination of object-oriented and generic programming styles and in our opinion this combination is optimal in terms of adaptability, efficiency and functionality. This means that developers can define their own models and integrate them into the framework with a minimum of programmer effort. In other words, the infrastructure is in place and all that needs to be done is to insert your own specific code and C++ classes. For example, it is possible to model a wide range of problems such as baskets, stochastic volatility and fixed income applications.

Finally, one of the advantages of having loosely-coupled components is that the software can be ported to a parallel environment; each component is (potentially) a parallel thread. Then we have the possibility to employ parallel design patterns such as Master-Slave, for example.

Daniel's Vlog: Creating Application Frameworks Using C++

Daniel discusses issues involved in creating application frameworks using C++ for Monte Carlo applications.

Email Daniel or leave a comment if you have any questions/feedback.

Joerg Kienitz: Monte Carlo now or Monte Carlo later?

Our quantitative finance team is involved in many parts of the banks business. We are not specialised to work in certain areas and markets like most quant teams in the city. We have to deal with a number of issues like portfolio optimisation, dynamic portfolio trading strategies or derivatives pricing. Furthermore, we have to consider the broad range of asset classes.

Because there is a limited amount of manpower available we look for methods that can be applied to a large class of problems. To this end we decided to implement some robust, flexible and widely applicable tools. One of those tools is the Monte Carlo method.

The Monte Carlo method can be applied to a wide range of problems in finance. We use it for examining dynamic trading strategies like CPPI, computing VaR and derivatives pricing.
Often Monte Carlo simulation is the only chance to get results. This is the case if you work on high dimensional, path-dependent problems. Monte Carlo simulation uses ideas from probability theory as well as calculus but also from number theory. There are many sources of input for new ideas and new methods. It is a very active field for researchers.

The method has – of course - some drawbacks. Some of the main criticisms put forward are that the procedure is time consuming when implemented on a computer and it is often hard to compute the Greeks and prices for American / Bermudan options. But latest research shows that difficulties can be overcome in applications. For example Giles and Glasserman developed new methods for computing Greeks or Schoenmakers tackled the problem for computing prices for Bermudan options in high dimensional Libor Market models.

Together with Daniel Duffy we work on a generic and robust method to implement the Monte Carlo method such that it can easily be extended and customised to fit your needs. This is hard work but we hope to come up with a nice setup.

The method of choice is programming in C++ using Microsoft Excel as a frontend. Excel is used for supplying data, outputting data and graphical display it. All the numerical stuff is done in C++. This gives us the opportunity to work object oriented and get speedy methods. 

The complexity of the models used for derivatives pricing and portfolio optimisation does certainly increase. Complex stochastic models are put forward to capture the features observed in the markets. The Gaussian paradigm does not hold any more!

Therefore: Monte Carlo now! Not later!

This is my answer to the initially posed question. I suggest to set up a robust and flexible Monte Carlo engine. Then, you are able to tackle a lot of problems in finance appropriately.

Any comments?!

Cheers, Joerg

Daniel Duffy: Monte Carlo Frameworks in C++: From Problem Domain to Working Code

In this blog I would like to give a bird’s-eye overview of some collaborative work with Dr. Jörg Kienitz of the German Postbank AG.

The main goal is to design, develop and deploy a customizable software system that can be adapted to suit different types of derivatives products and that meets certain performance criteria. In particular, we wish to calculate the price of a number of equity and interest rate products using the Monte Carlo (MC) method. The important thing to remember about the MC method is that it is robust, converges to an accurate solution in most cases and it can be applied to a range of problems that other methods are not able to solve. For this reason alone we are attempting to develop flexible frameworks using modern system and design patterns.

The language of choice is C++ and we have chosen it for a number of reasons, some of which are based on the simple fact that we know the language well, we like it and it is interoperable with many software libraries. It is also an industry standard. Finally, it supports the object-oriented, generic and modular programming techniques and we use all three metaphors to help us create software that is as flexible and malleable as possible.

Some of the major challenges (nice ones!) in this project are:

-Such a framework has not been attempted before to the best of our knowledge in the sense than we cannot see any results in published literature

-The project demands a number of skills such as finance, stochastic and MC theory, numerical analysis, design techniques, C++ and project management skills (the last in the sense that the project must be delivered 31 June 2007)

-The number of robust finite difference schemes that are able to approximate the solution of the Stochastic Differential Equations (SDE) that describe the behaviour of the underlying assets seems to be restricted to the Euler and Milstein methods and for this reason we are developing and applying other schemes that are applicable to a range of SDE. Much research needs to be done in this area

-Jörg and myself are located in different countries (Germany, Netherlands) which makes communication more difficult than if we were sitting in the same office. For this reason, we needed to develop a vocabulary which would allow us to impart ideas at a higher level than just ‘raw’ C++ code

-When the application is in the ‘get it working’ phase we wish to port it to MPI and OpenMP environments

In later blogs both JK and myself will discuss a number of related issues in more detail. For the moment, I would like to conclude the blog with a number of do’s and don’ts that we learned during this project (we are still learning):

Do’s
-Partition the problem into loosely coupled subsystems/component with well-defined interfaces
-Spend 30% of your time on design, 35% on programming. The rationale is that once you know what must be done then it is easy to do
-Adopt a multi-disciplinary and multi-paradigm approach
-Spiral, risk-driven, incremental project management model
-Make sure you learn C++ well to get optimal results

Don’ts
-Start the project by creating deep C++ class hierarchies; using inheritance is an optimization step in a sense. The hierarchy will come once you get the basic classes up and running; at all costs, avoid spaghetti code
-Try to make everything into an object. Not everything needs to be a class. And such a step may be semantically wrong. Nice class for the wrong problem
-Do not generalize until we have some specialisation (this means that were work with concrete examples at each stage of the project, it keeps us on the rails)

My next blog will be a video presentation ‘Daniel in the C++ Lion’s Den: Do’s and Don’ts when learning C++’. I dedicate it to my co-blogger Dr. Egor Kraev.

Daniel Duffy