Asynchronous iterations of parareal algorithm for option pricing models. (English) Zbl 1390.91323

Summary: Spatial domain decomposition methods have been largely investigated in the last decades, while time domain decomposition seems to be contrary to intuition and so is not as popular as the former. However, many attractive methods have been proposed, especially the parareal algorithm, which showed both theoretical and experimental efficiency in the context of parallel computing. In this paper, we present an original model of asynchronous variant based on the parareal scheme, applied to the European option pricing problem. Some numerical experiments are given to illustrate the convergence performance and computational efficiency of such a method.


91G60 Numerical methods (including Monte Carlo methods)
65M55 Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs
91G20 Derivative securities (option pricing, hedging, etc.)
Full Text: DOI


[1] Chartier, P.; Philippe, B.; A Parallel Shooting Technique for Solving Dissipative ODE’s; Computing: 1993; Volume 51 ,209-236. · Zbl 0788.65079
[2] Deuflhard, P.; ; Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms: Berlin/Heidelberg, Germany 2004; Volume Volume 35 . · Zbl 1056.65051
[3] Horton, G.; Stefan, V.; A Space-Time Multigrid Method for Parabolic Partial Differential Equations; SIAM J. Sci. Comput.: 1995; Volume 16 ,848-864. · Zbl 0828.65105
[4] Leimkuhler, B.; Timestep Acceleration of Waveform Relaxation; SIAM J. Numer. Anal.: 1998; Volume 35 ,31-50. · Zbl 0914.65077
[5] Gander, M.J.; Zhao, H.; Overlapping Schwarz Waveform Relaxation for the Heat Equation in N Dimensions; BIT Numer. Math.: 2002; Volume 42 ,779-795. · Zbl 1022.65112
[6] Gander, M.J.; Halpern, L.; Nataf, F.; Optimal Schwarz Waveform Relaxation for the One Dimensional Wave Equation; SIAM J. Numer. Anal.: 2003; Volume 41 ,1643-1681. · Zbl 1085.65077
[7] Lions, J.L.; Maday, Y.; Turinici, G.; Résolution d’EDP par Un Schéma en Temps “Pararéel”; Comptes Rendus de l’Académie des Sciences-Série I-Mathématique: 2001; Volume 332 ,661-668. · Zbl 0984.65085
[8] Farhat, C.; Chandesris, M.; Time-Decomposed Parallel Time-Integrators: Theory and Feasibility Studies for Fluid, Structure, and Fluid-Structure Applications; Int. J. Numer. Methods Eng.: 2003; Volume 58 ,1397-1434. · Zbl 1032.74701
[9] Chazan, D.; Miranker, W.; Chaotic Relaxation; Linear Algebra Appl.: 1969; Volume 2 ,199-222. · Zbl 0225.65043
[10] Miellou, J.C.; Algorithmes de Relaxation Chaotique à Retards; ESAIM Math. Model. Numer. Anal.: 1975; Volume 9 ,55-82. · Zbl 0329.65038
[11] Baudet, G.M.; Asynchronous Iterative Methods for Multiprocessors; J. ACM: 1978; Volume 25 ,226-244. · Zbl 0372.68015
[12] El Tarazi, M.N.; Some Convergence Results for Asynchronous Algorithms; Numer. Math.: 1982; Volume 39 ,325-340. · Zbl 0479.65030
[13] Miellou, J.C.; Spitéri, P.; Un Critère de Convergence pour des Méthodes Générales de Point Fixe; ESAIM Math. Model. Numer. Anal.: 1985; Volume 19 ,645-669. · Zbl 0606.65042
[14] Bertsekas, D.P.; Distributed Asynchronous Computation of Fixed Points; Math. Program.: 1983; Volume 27 ,107-120. · Zbl 0521.90089
[15] Bertsekas, D.P.; Tsitsiklis, J.N.; ; Parallel and Distributed Computation: Numerical Methods: Upper Saddle River, NJ, USA 1989; . · Zbl 0743.65107
[16] Magoulès, F.; Venet, C.; Asynchronous Iterative Sub-structuring Methods; Math. Comput. Simul.: 2018; Volume 145 ,34-49.
[17] Magoulès, F.; Szyld, D.B.; Venet, C.; Asynchronous Optimized Schwarz Methods with and without Overlap; Numer. Math.: 2017; Volume 137 ,199-227. · Zbl 1382.65449
[18] El Baz, D.; Spitéri, P.; Miellou, J.C.; Gazen, D.; Asynchronous Iterative Algorithms with Flexible Communication for Nonlinear Network Flow Problems; J. Parallel Distrib. Comput.: 1996; Volume 38 ,1-15.
[19] Miellou, J.C.; El Baz, D.; Spitéri, P.; A New Class of Asynchronous Iterative Algorithms with Order Intervals; AMS Math. Comput.: 1998; Volume 67 ,237-255. · Zbl 0899.65031
[20] Frommer, A.; Szyld, D.B.; Asynchronous Iterations with Flexible Communication for Linear Systems; Calculateurs Parallèles: 1998; Volume 10 ,91-103.
[21] Frommer, A.; Szyld, D.B.; On Asynchronous Iterations; J. Comput. Appl. Math.: 2000; Volume 123 ,201-216. · Zbl 0967.65066
[22] El Baz, D.; Frommer, A.; Spiteri, P.; Asynchronous Iterations with Flexible Communication: Contracting Operators; J. Comput. Appl. Math.: 2005; Volume 176 ,91-103. · Zbl 1069.65054
[23] Frommer, A.; Szyld, D.B.; Asynchronous Two-Stage Iterative Methods; Numer. Math.: 1994; Volume 69 ,141-153. · Zbl 0821.65010
[24] Bahi, J.M.; Contassot-Vivier, S.; Couturier, R.; ; Parallel Iterative Algorithms: From Sequential to Grid Computing: Boca Raton, FL, USA 2007; . · Zbl 1153.65004
[25] Black, F.; Scholes, M.; The Pricing of Options and Corporate Liabilities; J. Political Econ.: 1973; Volume 81 ,637-654. · Zbl 1092.91524
[26] Merton, R.C.; Theory of Rational Option Pricing; Bell J. Econ.: 1973; Volume 4 ,141-183. · Zbl 1257.91043
[27] Merton, R.C.; On the Pricing of Corporate Debt: The Risk Structure of Interest Rates; J. Financ.: 1974; Volume 29 ,449-470.
[28] Cox, J.C.; Ross, S.A.; The Valuation of Options for Alternative Stochastic Processes; J. Financ. Econ.: 1976; Volume 3 ,145-166.
[29] Harrison, J.M.; Kreps, D.M.; Martingales and Arbitrage in Multiperiod Securities Markets; J. Econ. Theory: 1979; Volume 20 ,381-408. · Zbl 0431.90019
[30] Cox, J.C.; Ross, S.A.; Rubinstein, M.; Option Pricing: A Simplified Approach; J. Financ. Econ.: 1979; Volume 7 ,229-263. · Zbl 1131.91333
[31] Hull, J.; White, A.; The Pricing of Options on Assets with Stochastic Volatilities; J. Financ.: 1987; Volume 42 ,281-300. · Zbl 1126.91369
[32] Duan, J.C.; The GARCH Option Pricing Model; Math. Financ.: 1995; Volume 5 ,13-32. · Zbl 0866.90031
[33] Itô, K.; ; On Stochastic Differential Equations: Providence, RI, USA 1951; .
[34] Bahi, J.M.; Domas, S.; Mazouzi, K.; Jace: A Java Environment for Distributed Asynchronous Iterative Computations; Proceedings of the 12th Euromicro Conference on Parallel, Distributed and Network-Based Processing: ; ,350-357.
[35] Bahi, J.M.; Couturier, R.; Vuillemin, P.; JaceV: A Programming and Execution Environment for Asynchronous Iterative Computations on Volatile Nodes; Proceedings of the 2006 International Conference on High Performance Computing for Computational Science, Rio de Janeiro: ; ,79-92.
[36] Bahi, J.M.; Couturier, R.; Vuillemin, P.; JaceP2P: An Environment for Asynchronous Computations on Peer-to-Peer Networks; Proceedings of the 2006 IEEE International Conference on Cluster Computing: ; ,1-10.
[37] Charr, J.C.; Couturier, R.; Laiymani, D.; JACEP2P-V2: A Fully Decentralized and Fault Tolerant Environment for Executing Parallel Iterative Asynchronous Applications on Volatile Distributed Architectures; Proceedings of the 2009 International Conference on Advances in Grid and Pervasive Computing: ; ,446-458.
[38] Couturier, R.; Domas, S.; CRAC: A Grid Environment to Solve Scientific Applications with Asynchronous Iterative Algorithms; Proceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium: ; ,1-8.
[39] Magoulès, F.; Gbikpi-Benissan, G.; JACK: An Asynchronous Communication Kernel Library for Iterative Algorithms; J. Supercomput.: 2017; Volume 73 ,3468-3487.
[40] Magoulès, F.; Gbikpi-Benissan, G.; JACK2: An MPI-based Communication Library with Non-blocking Synchronization for Asynchronous Iterations; Adv. Eng. Softw.: 2018; .
[41] Magoulès, F.; Cheik Ahamed, A.K.; Alinea: An Advanced Linear Algebra Library for Massively Parallel Computations on Graphics Processing Units; Int. J. High Perform. Comput. Appl.: 2015; Volume 29 ,284-310.
[42] Cheik Ahamed, A.K.; Magoulès, F.; Fast Sparse Matrix-Vector Multiplication on Graphics Processing Unit for Finite Element Analysis; Proceedings of the 14th IEEE International Confernence on High Performance Computing and Communications: ; .
[43] Magoulès, F.; Cheik Ahamed, A.K.; Putanowicz, R.; Fast Iterative Solvers for Large Compressed-Sparse Row Linear Systems on Graphics Processing Unit; Pollack Periodica: 2015; Volume 10 ,3-18.
[44] Cheik Ahamed, A.K.; Magoulès, F.; Iterative Methods for Sparse Linear Systems on Graphics Processing Unit; Proceedings of the 14th IEEE International Confernence on High Performance Computing and Communications: ; .
[45] Magoulès, F.; Cheik Ahamed, A.K.; Putanowicz, R.; Auto-Tuned Krylov Methods on Cluster of Graphics Processing Unit; Int. J. Comput. Math.: 2015; Volume 92 ,1222-1250. · Zbl 1314.65049
[46] Magoulès, F.; Cheik Ahamed, A.K.; Suzuki, A.; Green Computing on Graphics Processing Units; Concurr. Comput. Pract. Exp.: 2016; Volume 28 ,4305-4325.
[47] Magoulès, F.; Cheik Ahamed, A.K.; Putanowicz, R.; Optimized Schwarz Method without Overlap for the Gravitational Potential Equation on Cluster of Graphics Processing Unit; Int. J. Comput. Math.: 2016; Volume 93 ,955-980. · Zbl 1357.65040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.