Paper: arXiv 2303.02317

Authors: 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 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(\left(T\log^2{T}\right)/p + T)$ time under a greedy scheduler on $p$ processing cores, which is a significant improvement over the $Θ({T^2}/{p}) + Ω(T\log{T})$ time taken by the corresponding state-of-the-art parallel algorithm. Even when run on a single core, the $O(T\log^2{T})$ time taken by our algorithms is asymptotically much smaller than the $Θ(T^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 $T \approx 1000$ steps on a 48-core machine, our algorithm for the binomial model runs at least $15\times$ faster than the fastest existing parallel program for the same model with the speed-up factor gradually reaching beyond $500\times$ for $T \approx 0.5 \times 10^6$. It saves more than 80% energy when $T \approx 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(T^2)$ time. These contributions are of independent interest as stencil computations have a wide range of applications beyond quantitative finance.

Complexity vs Empirical Score

  • Math Complexity: 7.5/10
  • Empirical Rigor: 6.5/10
  • Quadrant: Holy Grail — high math complexity, high empirical rigor

Why this score: This paper presents a groundbreaking algorithmic advance, reducing the computational time complexity for pricing American options via finite-difference/stencil methods from quadratic to sub-quadratic using FFT techniques. It balances rigorous theoretical computer science proofs with impressive parallel computing benchmark performance and energy efficiency metrics.

Research Flowchart

  flowchart TD
    A[Goal: Fast American Option Pricing via Nonlinear Stencils] --> B[Input: Financial Models & Parameters<br><i>Binomial, Trinomial, Black-Scholes-Merton</i>]
    B --> C[Method: Reformulate Finite-Difference Stencils<br>using Fast Fourier Transform]
    C --> D[Execution: Parallel Processing<br>via Greedy Scheduler on p Cores]
    D --> E[Outcome: O-T log² T / p + T Time Complexity<br><i>vs. traditional Θ-T² / p</i>]
    E --> F[Empirical Results: Up to 500x Speedup & >99% Energy Savings]