×

zbMATH — the first resource for mathematics

Parallelizing computation of expected values in recombinant binomial trees. (English) Zbl 07192573
Summary: Recombinant binomial trees are binary trees where each non-leaf node has two child nodes, but adjacent parents share a common child node. Such trees arise in option pricing in finance. For example, an option can be valued by evaluating the expected payoffs with respect to random paths in the tree. The cost to exactly compute expected values over random paths grows exponentially in the depth of the tree, rendering a serial computation of one branch at a time impractical. We propose a parallelization method that transforms the calculation of the expected value into an embarrassingly parallel problem by mapping the branches of the binomial tree to the processes in a multiprocessor computing environment. We also discuss a parallel Monte Carlo method and verify the convergence and the variance reduction behavior by simulation study. Performance results from R and Julia implementations are compared on a distributed computing cluster.
Reviewer: Reviewer (Berlin)
MSC:
62 Statistics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cox JC, Ross SA, Rubinstein M.Option pricing: a simplified approach. J Financ Econ. 1979;7(3):229-263. [cited 2017 Nov 15]. Available from: http://www.sciencedirect.com/science/article/pii/0304405X79900151 doi: 10.1016/0304-405X(79)90015-1[Crossref], [Web of Science ®], [Google Scholar] · Zbl 1131.91333
[2] Hull JC. Options, futures, and other derivatives. New Delhi: Prentice Hall; 2003. [Google Scholar] · Zbl 1087.91025
[3] Seydel R. Tools for computational finance. Berlin: Springer; 2003. [Google Scholar] · Zbl 1044.91534
[4] Little RJA.Pattern-mixture models for multivariate incomplete data. J Amer Statist Assoc. 1993;88(421):125-134. [Taylor & Francis Online], [Web of Science ®], [Google Scholar] · Zbl 0775.62134
[5] Hosseini M, Neerchal NK, Gruber-Baldini AL. Statistical modeling of subject and proxy observations using weighted GEE. In: JSM Proceedings, Section on Statistics in Epidemiology. Alexandria, VA: American Statistical Association; 2016. p. 1101-1111. [Google Scholar]
[6] Glasserman P. Monte carlo methods in financial engineering. 1st ed.New York (NY): Springer; 2003. [Crossref], [Google Scholar] · Zbl 1038.91045
[7] Pacheco PS. Parallel programming with mpi. San Francisco (CA): Morgan Kaufmann; 1997. [Google Scholar] · Zbl 0877.68013
[8] Foster I. Designing and building parallel programs: concepts and tools for parallel software engineering. Reading (MA): Addison-Wesley; 1995. [Google Scholar] · Zbl 0844.68040
[9] Ganesan N, Chamberlain RD, Buhler J. Acceleration of binomial options pricing via parallelizing along time-axis on a GPU. Proc of Symp on Application Accelerators in High Performance Computing; Urbana, IL; 2009. [Google Scholar]
[10] Kolb C, Pharr M. Option pricing on the GPU in GPU gems 2. Addison-Wesley; 2005. [cited 2017 Nov 15]. Available from: https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_inside_front_cover.htmlhttps://developer.nvidia.com/gpugems/GPUGems2/gpugems2_inside_front_cover.html [Google Scholar]
[11] Popuri SK, Raim AM, Neerchal NK, et al. An implementation of binomial method of option pricing using parallel computing. UMBC High Performance Computing Facility, University of Maryland, Baltimore County; 2013. Technical Report HPCF-2013-1. [cited 2017 Nov 15]. Available from: https://hpcf.umbc.edu/publications[Google Scholar]
[12] Swarztrauber PN, Sweet RA.Vector and parallel methods for the direct solution of Poisson’s equation. J Comput Appl Math. 1989;27:241-263. doi: 10.1016/0377-0427(89)90369-5[Crossref], [Web of Science ®], [Google Scholar] · Zbl 0677.65097
[13] Boyle PP.Option valuation using a three-jump process. Int Options J. 1986;3:7-12. [Google Scholar]
[14] Rubinstein RY, Kroese DP. Simulation and the Monte Carlo method. Hoboken State (NJ): John Wiley and Sons; 2008. [Google Scholar] · Zbl 1147.68831
[15] Gabriel E, Fagg GE, Bosilca G, et al. Open MPI: goals, concept, and design of a next generation MPI implementation. In: Proceedings, 11th European PVM/MPI Users Group Meeting; Sept; Budapest, Hungary; 2004. [Google Scholar]
[16] R Core Team. R: A language and environment for statistical computing. Vienna, Austria: R Foundation for Statistical Computing; 2012. ISBN 3-900051-07-0; [cited 2017 Nov 15]. Available from: http://www.r-project.org[Google Scholar]
[17] Yu H. Rmpi: Parallel statistical computing in R. R News. 2002;2(2):10-14. [cited 2017 Nov 15]. Available from: http://cran.r-project.org/doc/Rnews/Rnews_2002-2.pdf[Google Scholar]
[18] Ostrouchov G, Chen WC, Schmidt D, et al. Programming with big data in R; 2012. [cited 2017 Nov 15]. Available from: http://r-pbd.org/. [Google Scholar]
[19] Eddelbuettel D, François R.Rcpp: Seamless R and C++ integration. J Statist Softw. 2011;40(8):1-18. [cited 2017 Nov 15]. Available from: http://www.jstatsoft.org/v40/i08/ doi: 10.18637/jss.v040.i08[Crossref], [Web of Science ®], [Google Scholar]
[20] Bezanson J, Edelman A, Karpinski S, et al. Julia: A fresh approach to numerical computing. 2014. [cited 2017 Nov 15]. Available from: https://arxiv.org/abs/1411.1607. [Google Scholar] · Zbl 1356.68030
[21] Lattner C, Adve V. LLVM: A compilation framework for lifelong program analysis & transformation. In: Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO’04); Mar; Palo Alto, California; 2004. [Google Scholar]
[22] Noack A. Julia - MPI package; 2016. [cited 2017 Nov 15]. Available from: https://github.com/JuliaParallel/MPI.jl[Google Scholar]
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.