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^2 T ) / 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 ≈ 1000 steps on a 48-core machine, our algorithm for the binomial model runs at least 15x faster than the fastest existing parallel program for the same model with the speed-up factor gradually reaching beyond 500x for T ≈ 0.5 x 10^6. 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(T^2) time. These contributions are of independent interest as stencil computations have a wide range of applications beyond quantitative finance.