Hacker News Reader

Comment by srean | Hacker News Reader

Had the following thought just to entertain myself, I don't expect it to have any utility in practice, but here goes:

Take a small interval around your smooth function that includes the point where you want to compute the derivative. Joint the right and left ends by just reflecting itself, so that you have a differentiable periodic function. Now sample that at a suitable rate, take its FFT, derive the FFT of the derivative by multiplying it with 2\pi I. Take the inverse FFT and evaluate it at the point of interest. May be useful if you want to compute the derivative at many points, but seems wasteful otherwise.

One of course has to dot the i's and cross the t's (of aliasing effects, Nyquist limits etc). Perhaps some other fast integral transform would work even better. I will be surprised if there isn't an old industry around it.

View on HN

This is called a spectral method and is widely used in numerical codes.

I highly recommend Spectral Methods in MATLAB by Trefethen (who someone mentions above) for a very good tutorial. You can freely ignore the MATLAB part and use whatever programming language you want, as long as you have an FFT routine.

Thanks for pointing to the right direction in case I want scratch that itch more. I am not surprised though that this has been done, expected the same. From a quick look, no one seems to suggest reflecting the original analytic function to get a periodic function, I guess some caveats lurk there.

Does other integral transforms work better than Fourier ?

When you use this method you are implicitly making the function periodic. I can give you any function on some interval (sufficiently well behaved) and you can compute the Fourier series of it. Even though it's only defined on the interval, if you plotted the Fourier series you would still find it to be periodic. The same idea carries over to the spectral derivative. Even if the function isn't periodic, the method still works, it's just that the numerics near the discontinuity are going to be crap and can affect things further away. But if you are sufficiently far away, things are kosher. Note there are ways of dealing with this using Chebyshev interpolation (see http://math.mit.edu/~stevenj/fft-deriv.pdf section 6) which Trefethen's book also discusses.

And no FFTs are the only transformations I am aware of. I've never heard of anyone using other transformations in a general numerical context, outside of specialized problems.

Given the local nature of the problem and the potential for using O(n) operations (as opposed n log n) my first suspect was wavelet transforms and sure enough people have done that but that body of work seems more recent than the use of FFT.

Reply on news.ycombinator.com