# How to use fast Fourier transforms (FFT) to calculate derivatives of a function?

Suppose we have a function numerically defined at pseudospectral collocation points

nx = 12;
x = -N[Table[Cos[(j Pi)/nx], {j, 0, nx}]]
(* -> {-1., -0.965926, -0.866025, -0.707107, -0.5, -0.258819, 0., 0.258819, 0.5, 0.707107, 0.866025, 0.965926, 1.} *)


Take the following f as an example

f = Exp[x] + x^2;
(* -> {1.36788, 1.31364, 1.17062, 0.993069, 0.856531, 0.83895, 1., 1.36239, 1.89872, 2.52811, 3.12744, 3.56023, 3.71828} *)


We want to calculate the derivative of f with respect to x. This can be achieved by multiplying f by the following differentiation matrix dx

dx = NDSolveFiniteDifferenceDerivative[1, x, DifferenceOrder -> "Pseudospectral"]["DifferentiationMatrix"];
dx.f
(* -> {-1.63212, -1.55122, -1.31143, -0.921145, -0.393469, 0.254325, 1., 1.81304, 2.64872, 3.44233, 4.10949, 4.55907, 4.71828} *)


In the tutorial The Numerical Method of Lines,

For pseudospectral derivatives, which can be computed using fast Fourier transforms, it may be faster to use the differentiation matrix for small size, but ultimately, on a larger grid, the better complexity and numerical properties of the FFT make this the much better choice.

How to obtain pseudospectral derivatives of the above function f by FFT?

• – Michael E2 Sep 21 '18 at 10:26

NDSolveFiniteDifferenceDerivative[1, x, f, DifferenceOrder -> "Pseudospectral"]

func = NDSolveFiniteDifferenceDerivative[1, x, DifferenceOrder -> "Pseudospectral"]

• This is significantly faster than dx.f for large nx, implying that func[f]` uses FFT internally. – renphysics Sep 21 '18 at 13:00