Fast American Option Pricing using Nonlinear Stencils

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 ((T log² T)/P + T) time under a greedy scheduler on P processing cores, which is a significant improvement over the Θ (T²/P) + Ω (T logT) time taken by the corresponding state-of-the-art parallel algorithm. Even when run on a single core, the O (T log² T) time taken by our algorithms is asymptotically much smaller than the Θ (T²) 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 speedup factor gradually reaching beyond 500× for T ≈ 0.5 × 10⁶. It saves more than 80% energy when T ≈ 4000, and more than 99% energy for T > 60, 000. Our 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 (T²) time. These contributions are of independent interest as stencil computations have a wide range of applications beyond quantitative finance.