2023/03/04 by Zafar Ahmad, Ahmad, Zafar, Rezaul Chowdhury +8
Computer Science · Economics, Econometrics and Finance · #Advanced Data Storage Technologies #Computational Engineering #Computational Finance (q-fin.CP) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Economics and business #Finance #Parallel Computing and Optimization Techniques #Stochastic processes and financial applications #and Science (cs.CE)
paper · pdf · doi:10.48550/arxiv.2303.02317
openalex publication_date 2023/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the binomial, trinomial, and Black-Scholes-Merton models of option pricing. We present fast parallel discrete-time finite-difference algorithms for American call option pricing under the binomial and trinomial models and American put option pricing under the Black-Scholes-Merton model. For T-step finite differences, each algorithm runs in O((Tlog2T)/p + T) time under a greedy scheduler on p processing cores, which is a significant improvement over the Θ(T2/p) + Ω(TlogT) time taken by the corresponding state-of-the-art parallel algorithm. Even when run on a single core, the O(Tlog2T) time taken by our algorithms is asymptotically much smaller than the Θ(T2) running time of the fastest known serial algorithms. Implementations of our algorithms significantly outperform the fastest implementations of existing algorithms in practice, e.g., when run for T ≈ 1000 steps on a 48-core machine, our algorithm for the binomial model runs at least 15× faster than the fastest existing parallel program for the same model with the speed-up factor gradually reaching beyond 500× for T ≈ 0.5 × 106. It saves more than 80% energy when T ≈ 4000, and more than 99% energy for T > 60,000. Our option pricing algorithms can be viewed as solving a class of nonlinear 1D stencil (i.e., finite-difference) computation problems efficiently using the Fast Fourier Transform (FFT). To our knowledge, ours are the first algorithms to handle such stencils in o(T2) time. These contributions are of independent interest as stencil computations have a wide range of applications beyond quantitative finance.