Fast American Option Pricing using Nonlinear Stencils
Zafar Ahmad, Reilly Browne, Rezaul Chowdhury, Rathish Das, Yushen Huang, Yimin Zhu
Abstract
We study the binomial, trinomial, and Black-Scholes-Merton models of option pricing. We present fast parallel discretetime 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 ๐ -step finite differences, each algorithm runs in O ๐ log 2 ๐ /๐ + ๐ time under a greedy scheduler on ๐ processing cores, which is a significant improvement over the ฮ ๐ 2 /๐ + ฮฉ (๐ log๐ ) time taken by the corresponding state-of-the-art parallel algorithm. Even when run on a single core, the O ๐ log 2 ๐ time taken by our algorithms is asymptotically much smaller than the ฮ ๐ 2 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 ๐ โ 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 speedup factor gradually reaching beyond 500ร for ๐ โ 0.5 ร 10 6 . It saves more than 80% energy when ๐ โ 4000, and more than 99% energy for ๐ > 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 ๐ ๐ 2 time. These contributions are of independent interest as stencil computations have a wide range of applications beyond quantitative finance.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Pencil: a pipelined algorithm for distributed stencilsHengjie Wang, Aparna ChandramowlishwaranSC 2020 ยท 12 citations
- Volumetric Optimal Transportation by Fast Fourier TransformNa Lei, Dongsheng An, Min Zhang, Xiaoyin Xu et al.ICLR 2023
- Exploring Efficient Partial Differential Equation Solution Using Speed Galerkin TransformerXun Wang, Zeyang Zhu, Xiangyu Meng, Tao SongSC 2024
- Automatic Generation of Mappings for Distributed Fourier OperationsDoru-Thom Popovici, Botao Wu, John Shalf, Martin KongSC 2025 ยท 3 citations
- PAGANI: a parallel adaptive GPU algorithm for numerical integrationIoannis Sakiotis, Kamesh Arumugam, Marc F. Paterno, Desh Ranjan et al.SC 2021 ยท 4 citations
