Numerical analysis
The parareal algorithm for American options
Comptes Rendus. Mathématique, Volume 354 (2016) no. 11, pp. 1132-1138.

This note provides a description of the parareal method for American contracts, a numerical section to assess its performance. The scalar case is investigated. Least-Square Monte Carlo (LSMC) and parareal time decomposition with two or more levels are used, leading to an efficient parallel implementation. It contains also a convergence argument for the two-level parareal Monte Carlo method when the time step used for the Euler scheme at each level is appropriate. This argument provides also a tool for analyzing the multilevel case.

Dans cette note, la méthode pararéelle est introduite pour le calcul d'options américaines. L'algorithme LSMC (Least-Square Monte Carlo) de Longstaff–Schartz est parallélisé grâce à une décomposition en temps multi-niveaux. Dans une section numérique, les performances de la méthode sont données dans deux cas scalaires. Un résultat partiel de convergence est énoncé lorsque la méthode d'Euler explicite est utilisée avec des pas de temps appropriés sur chaque niveau. Une estimation est obtenue, qui permet d'analyser la méthode pararéelle multi-niveaux.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2016.09.010
Pagès, Gilles 1; Pironneau, Olivier 2; Sall, Guillaume 1, 2

1 Laboratoire de probabilités et modèles aléatoires, UMR 7599, case 188, 4, place Jussieu, 75252 Paris cedex 05, France
2 Laboratoire Jacques-Louis-Lions, UMR 7598, case 187, 4, place Jussieu, 75252 Paris cedex 05, France
@article{CRMATH_2016__354_11_1132_0,
     author = {Pag\`es, Gilles and Pironneau, Olivier and Sall, Guillaume},
     title = {The parareal algorithm for {American} options},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1132--1138},
     publisher = {Elsevier},
     volume = {354},
     number = {11},
     year = {2016},
     doi = {10.1016/j.crma.2016.09.010},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2016.09.010/}
}
TY  - JOUR
AU  - Pagès, Gilles
AU  - Pironneau, Olivier
AU  - Sall, Guillaume
TI  - The parareal algorithm for American options
JO  - Comptes Rendus. Mathématique
PY  - 2016
SP  - 1132
EP  - 1138
VL  - 354
IS  - 11
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2016.09.010/
DO  - 10.1016/j.crma.2016.09.010
LA  - en
ID  - CRMATH_2016__354_11_1132_0
ER  - 
%0 Journal Article
%A Pagès, Gilles
%A Pironneau, Olivier
%A Sall, Guillaume
%T The parareal algorithm for American options
%J Comptes Rendus. Mathématique
%D 2016
%P 1132-1138
%V 354
%N 11
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2016.09.010/
%R 10.1016/j.crma.2016.09.010
%G en
%F CRMATH_2016__354_11_1132_0
Pagès, Gilles; Pironneau, Olivier; Sall, Guillaume. The parareal algorithm for American options. Comptes Rendus. Mathématique, Volume 354 (2016) no. 11, pp. 1132-1138. doi : 10.1016/j.crma.2016.09.010. http://www.numdam.org/articles/10.1016/j.crma.2016.09.010/

[1] Abbas-Turki, L.; Lapeyre, B. American option pricing on multi-core graphic cards, BIFE 2009, Beijing, China, 24–26 July 2009 (2009)

[2] Achdou, Y.; Pironneau, O. Computation Methods for Option Pricing, Frontiers in Applied Mathematics, SIAM, Philadelphia, 2005 (xviii + 297 p) (ISBN: 0-89871-573-3)

[3] Aitsahlia, F.; Carr, P. American options: a comparison of numerical methods (Rogers, L.C.G.; Talay, D., eds.), Numerical Methods in Finance, Publications of the Newton Institute, Cambridge University Press, Cambridge, UK, 1997, pp. 67-87

[4] Bal, G.; Maday, Y. A “parareal” time discretization for non-linear PDE's with application to the pricing of an American put, Zurich, Switzerland, 7–8 June 2001 (Pavarino, L.F.; Toselli, A., eds.), Volume vol. 23, Springer-Verlag, Berlin, Heidelberg, New York (2002), pp. 189-202

[5] Bally, V.; Pagès, G. A quantization algorithm for solving discrete time multidimensional optimal stopping problems, Bernoulli, Volume 6 (2003), pp. 1003-1049

[6] Benguigui, M. Valorisation d'options américaines et Value-At-Risk de portefeuille sur cluster de GPUs\CPUs, Université de Nice Sophia Antipolis, France, 2015 (Ph.D. thesis)

[7] M. Benguigui, F. Baude, Towards parallel and distributed computing on GPU for American basket option pricing, in: Proc. International Workshop on GPU Computing in Cloud in conjunction with 4th IEEE International Conference on Cloud Computing Technology and Science, Taipei, Taiwan, 3–6 December 2012.

[8] Caverhill, A.P.; Webber, N. American options: theory and numerical analysis (Hodges, S., ed.), Options: Recent Advances in Theory and Practise, Manchester University Press, Manchester, UK, 1990, pp. 80-94

[9] Clément, E.; Lamberton, D.; Protter, P. An analysis of a least squares regression method for American option pricing, Finance Stoch., Volume 6 (2002), pp. 449-471

[10] Cox, J.C.; Ingersoll, J.E.; Ross, S.A. A theory of the term structure of interest rates, Econometrica, Volume 53 (1985), pp. 385-407

[11] Dang, D.M.; Christara, C.C.; Jackson, K.R. An efficient graphics processing unit-based parallel algorithm for pricing multi-asset American options, Concurr. Comput., Volume 24 (2012) no. 18, pp. 849-866

[12] M. Fatica, E. Phillips, Pricing American options with least squares Monte Carlo on GPUs, in: Proc. 6th Workshop on High-Performance Computational Finance, Denver, CO, USA, 17–22 November 2013,.

[13] Gander, M.; Vandewalle, S. Analysis of the parareal time-parallel, time-integration method, SIAM J. Sci. Comput., Volume 29 (2007) no. 2, pp. 556-578

[14] Girard, J.-Y.; Toke, I.M. Monte Carlo valuation of multidimensional American option through grid computing, Lect. Notes Comput. Sci., vol. 3743, 2006, pp. 462-469

[15] Hu, Y.; Lu, Q.; Cao, Z.; Wang, J. Parallel simulation of high-dimensional American option pricing based on CPU versus MIC, Concurr. Comput., Volume 27 (2015) no. 15, pp. 1110-1121

[16] Khodja, L.; Girard, J.-Y.; Couturier, R.; Spitéri, P. Parallel solution of American option derivatives on GPU clusters, Comput. Math. Appl., Volume 65 (2013) no. 111, pp. 1830-1848

[17] Kloeden, P.; Platen, E. Numerical Solution of Stochastic Differential Equations, Applications of Mathematics, vol. 23, Springer-Verlag, Berlin, 1999

[18] Lions, J.-L.; Maday, Y.; Turinici, G. Résolution d'edp par un schéma en temps “pararéel”, C. R. Acad. Sci. Paris, Ser. I, Volume 332 (2000), pp. 661-668

[19] Longstaff, F.A.; Schwartz, E.S. Valuing American options by simulation: a simple least squares approach, Rev. Financ. Stud., Volume 14 (2001), pp. 113-148

[20] Pagès, G. Introduction to numerical probability for finance, 2016 http://www.proba.jussieu.fr/dw/lib/exe/fetch.php?media=users:pages:probnum_gilp_pf16.pdf (available at: 354 p)

[21] Pagès, G.; Wilbertz, B. GPGPUs in computational finance: massive parallel computing for American style options, Concurr. Comput., Volume 24 (2012) no. 18, pp. 837-848

[22] Wan, J.; Lai, K.; Kolkiewicz, A.; Tan, K. A parallel quasi-Monte Carlo approach to pricing American options on multiple assets, Int. J. High. Perform. Comput. Networking, Volume 4 (2006), pp. 321-330

Cited by Sources: