# SC²S Colloquium - July 26, 2012

Date: |
June 26, 2012 |

Room: |
02.07.023 |

Time: |
3 pm, s.t. |

## Contents

- 1 Samuel Maurus: A multi-dimensional PDE solver for option pricing based on the Heston model and sparse grids
- 2 Dominik Huth: Application of Multilevel Monte Carlo simulation to Barrier, Asian and American options
- 3 Nikolay Lukash: On Sparse Approximate Inverse Preconditioners
- 4 Julius Adorf: Non-linear clustering on sparse-grids

## Samuel Maurus: A multi-dimensional PDE solver for option pricing based on the Heston model and sparse grids

The pricing of non-trivial financial options must in general be performed using numerical techniques. This thesis presents a practical implementation of a deterministic option-equation solver based on Heston's stochastic volatility model - a model which generalises on that of Black-Scholes. The solver uses a finite-element approach based on sparse grids for spatial discretisation. Grid adaptivity is used to refine sensitive regions in the problem space. The solver supports the pricing of European basket call and put options without the drawback of slow convergence that typically accompanies non-deterministic techniques.

Results from the solver for vanilla options are provided and compared to Heston's closed-form solution as well as to an existing numerical solver (based on the Black-Scholes model). Results for basket options with up to three underlyings (problem dimensionality of six) are also provided and compared with existing Monte-Carlo results. Conclusions are made on the applicability of the solver and recommendations for further work in the area are given.

## Dominik Huth: Application of Multilevel Monte Carlo simulation to Barrier, Asian and American options

Monte Carlo simulation is a widely used method in option pricing. Its generic nature permits the application in a wide range of pricing problems, especially problems where the high dimensionality of the product makes PDE methods infeasible. A downside of Monte Carlo simulations is the relatively slow convergence rate of O(N^(1/2), i.e. to increase accuracy by a factor of N, the number of samples has to be increased by a factor of N^2. Although complexity cannot be changed, a constant speedup is possible. As one recent development, the Multilevel Monte Carlo (MLMC) method proposed by Giles calculates option prices on different timegrids and combines the results in a way to minimize the variance. We present MLMC results on Asian, Barrier, and American options in the Black-Scholes model and compare them to analytic or high-precision PDE solutions. Whereas the method is not suited for the generic pricing of Barrier options, it yields a variance reduction of up to a factor of 5 when applied to Asian and American options.

## Nikolay Lukash: On Sparse Approximate Inverse Preconditioners

For the solution of large systems of linear equations, iterative solvers with preconditioners are typically employed. However, the design of preconditioners for the black-box case, in which no additional information about the underlying problem is known, is very difficult. The most commonly employed method of incomplete LU factorizations is a serial algorithm and thus not well suited for parallel computing architectures. We investigate sparse approximate inverse preconditioners in this work, which show a very high degree of parallelism. The special case for block-structured matrices is considered. Implementation for the general case (BSPAI) and the factorized case (BFSPAI) will be done by means of a multithreaded environment using the LAPACK library. The preconditioner will be instantiated as a class that can be used for iterative solvers such as the conjugate gradient and the biconjugate gradient stabilized method. Preliminary benchmark results that demonstrate the benefits of the current implementation will be provided.

## Julius Adorf: Non-linear clustering on sparse-grids

This work applies a recent sparse-grid-based spectral clustering method to the problem of unsupervised image segmentation. The applicability of the method is tested on synthetic images, as well as on images from the Berkeley Segmentation Dataset. The impact of parameters is examined, focusing on the level of the sparse grid, the number of clusters, and the width of the similarity kernel. Serving as an automated alternative to manual model selection, the balanced linefit criterion is tested. The effects of hierarchical surplus refinement are studied and compared with variants introduced in this work, aiming at achieving good results with few grid points.