Efficient solution of a partial integro-differential equation in finance

Jump-diffusion models for the pricing of derivatives lead under certain assumptions to partial integro-differential equations (PIDE). Such a PIDE typically involves a convection term and a non-local integral. We transform the PIDE to eliminate the convection term, discretize it implicitly, and use finite differences on a uniform grid. The resulting dense linear system exhibits so much structure that it can be solved very efficiently by a circulant preconditioned conjugate gradient method. Therefore, this fully implicit scheme requires only on the order of O(nlogn) operations. Second order accuracy is obtained numerically on the whole computational domain for Merton's model.