How can the claims of this paper be true (on speed of Carr-Madan method for option pricing)?

Question

https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2815371

This paper states that a strike-optimized version of the Carr-Madan method for option pricing is faster than the original equivalent that uses FFT.

As you may recall, Carr-Madan formula states that the call price is $$C(k) = \frac{e^{-ak}}{\pi}\int_0^\infty e^{-ivk} \psi(v) dv$$ where $k = \log K$ (log-strike), and $\psi(v)$ is analytically known if we know the characteristic function of the log-spot.

Due to the nature of the integral, it is obvious that we can calculate it, for many $k$, using some sort of FFT-procedure. This is done in the original paper by Carr and Madan.

However, the paper linked to above states that it is faster (and inside the paper, apparently it is faster by several orders of magnitude) by just using direct integration in the above integral, using the fact that $\psi(v)$ is independent of $k$. I am not sure how exactly they implemented it, but I imagine it would be some sort of quadrature-rule combined with a matrix product calculation, such that the calculation of $\psi(v)$ is re-used for all $k$.

I do not believe that this method is faster. Can anybody verify the results of the paper, or link to other papers stating the same thing?

The FFT method is of order $O(N \log N)$. That is pretty damn quick.

This other method ... I mean, yes, by re-using $\psi(v)$, we'll be able to do it a little bit faster, but the method still seems $O(NK)$ to me, where $K$ is the number of strikes we are pricing. So it should be slower?

Answer 1

The answer by Enrico misses the point.

The integral contains the factor $e^{-ivk}$. If you have $K$ strikes and $N$ terms in the discrete approximation of the integral, you need to calculate $e^{-ivk}$ $KN$ times. If you're pricing 200 strikes and you take $N = 4096$, as is recommended by Carr-Madan, then $KN = 819.200$. Computing these values (and storing them) will be expensive.

So no, for similar $N$, the direct integration is not faster. It is asinine to even suggest otherwise. The FFT is known for it's speed, and now we want to pretend direct integration is suddenly faster? What? Please, people, educate yourselves.

But the point is that direct integration is more accurate. Hence, $N$ can be chosen to be much, much smaller than $4096$. Hence, in that sense, direct integration can be faster, simply because it will require less work to get a better accuracy.

For example, try to run the direct integration yourself using a simple sum-discretization. You will find that $N = 100$ works just fine for extreme accuracy.

Answer 2

I did not check in detail the paper you cited, but let me make two remarks. First, the speed of a computation depends a lot on the implementation (computing environment, language, ...). And authors may spend more time on tweaking the methods they advocate than on benchmark methods.

That being said, it may well be that direct integration is faster than using the FFT. When one prices options across many strikes and maturities, the characteristic function is independent of the strikes; so its needs only be evaluated once per maturity. And the characteristic function is (by far) the most expensive part of the whole computation. The actual integration is very fast if the the nodes/weights are precomputed: the integration reduces to multiplications and additions. (Using a high-level, adapative scheme would be much slower.)

The following reference discusses the direct approach and comes to a similar conclusion to the paper you cited. (It was later published, but I prefer the old source because it shows that the idea has been around for some time.)

@ARTICLE{,
         author  = {Fiodar Kilin},
         title   = {Accelerating the Calibration of Stochastic Volatility Models},
         journal = {Centre for Practical Quantitative Finance Working Paper Series No. 6},
         year    = 2007
}