One of the main difficulties lies on the fact that the Black-Scholes equation is defined on an unbounded domain. This difficulty is solved by considering the problem on a very large bounded domain. It can be proved that using this technique, an exact solution is reached. Thus, we have to solve very large problems.

The Euler implicit time marching scheme has been used for the discretization of the evolution part. Besides, the domain is discretized with a uniform mesh and for the spatial part of the problem, a finite difference method is used. Thus, the numerical solution consists of solving a large linear algebraic system at each time step. So, it is necessary to use parallel iterative methods.

The solution of algebraic systems is carried out with parallel projected block relaxation algorithms and a parallel projected Richardson method. The iterative scheme can be synchronous or asynchronous (i.e. computations are carried out in parallel without order nor synchronization, so processors go at their own pace according to their intrinsic characteristics and computational load). The use of an appropriate spatial discretization scheme leads to very interesting properties of the matrices to invert, ensuring the convergence of both iterative algorithms [1,2].

The implementation is carried out with MPI facilities according to the SPMD paradigm on the Grid5000 platform, a distributed and heterogeneous architecture. Each process initializes its own data set. The iterative algorithm is chosen at the beginning.

We have used up to 360 cores located at up to three distant sites. Results show that all asynchronous schemes of computation scale better than the synchronous ones, as a result of the lower sensitivity to granularity, network bandwidth, latency and load unbalancing issues. Asynchronous schemes are more adapted to the heterogeneous and distant distributed clusters than the synchronous ones.

1

J. Miellou, P. Spiteri, "Un critère de convergence pour des méthodes générales de point fixe", M2AN, 19, 645-669, 1985.

2

P. Spiteri, M. Chau, "Parallel asynchronous Richardson method for the solution of obstacle problem", in J.N. Almhana, V.C. Bhavsar, (Editors), "Proceedings of the 16th Annual International Symposium on HPCS", IEEE, 133-138, 2002. doi:10.1109/HPCSA.2002.1019146

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)