Pricing multi-asset American options on Graphics Processing Units using a PDE approach

We develop highly efficient parallel pricing methods on Graphics Processing Units (GPUs) for multi-asset American options via a Partial Differential Equation (PDE) approach. The linear complementarity problem arising due to the free boundary is handled by a penalty method. Finite difference methods on uniform grids are considered for the space discretization of the PDE, while classical finite differences, such as Crank-Nicolson, are used for the time discretization. The discrete nonlinear penalized equations at each timestep are solved using a penalty iteration. A GPU-based parallel Alternating Direction Implicit Approximate Factorization technique is employed for the solution of the linear algebraic system arising from each penalty iteration. We demonstrate the efficiency and accuracy of the parallel numerical methods by pricing American options written on three assets.

I. Introduction

The pricing of an American option is a challenging task, mainly due to the early exercise feature of the option, which leads to an additional constraint that the value of an American option must be greater than or equal to its payoff [14]. This constraint requires special treatment, a fact that makes an explicit closed form solution for an American option intractable for most cases. Consequently, numerical methods must be used. Recently, multi-asset options, i.e. options written on more than one underlying asset, have become increasingly popular. The problem of pricing multi-asset American options is not only mathematically challenging but also very computationally intensive. As a result, there is great interest in developing efficient numerical methods for pricing multi-asset American options.