  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 $\Theta({T^2}/{p}) + \Omega(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 $\Theta(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.
