Re: FFT Speed
- To: mathgroup at smc.vnet.net
- Subject: [mg121985] Re: FFT Speed
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Sat, 8 Oct 2011 05:32:30 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <201110070848.EAA07438@smc.vnet.net>
On 10/07/2011 03:48 AM, to wrote:
> I have a 3D matrix with dimensions {355,647,8}. For each {x,y} I need
> to compute the FFT along the z dimension, i.e. 355*647 FFTs of 8
> elements each. The fastest way I found to do this was
>
> Partition[Map[Fourier[#, FourierParameters -> {1, -1}]&,
> Flatten[data, 1]], dimx];
>
> I was wondering if there are faster ways to do this. The reason I ask
> is because another package for numerical computations can do this a
> lot faster compared to my solution (nearly two orders of magnitude
> faster !)
>
> I tried using ParallelMap but this makes things even slower.
I do not know why it is slow but I'll venture a guess. Possibly it
spends far more time in preprocessing overhead of Fourier, for each
call, than in the actual computation itself. This is particularly likely
given that the actual computations involve small lists.
A way around that is to do it as a matrix multiplication. This loses the
asymptotic efficiency of the FFT but for size 8 that efficiency was not
present to begin with.
fftmat[n_, a_, b_] :=
1/n^((1 - a)/2)*
Table[Exp[2*Pi*I*j*k*b/n], {j, 0, n - 1}, {k, 0, n - 1}]
f8mat = N[fftmat[8, 1, -1]];
mat = RandomReal[{-10, 10}, {355, 647, 8}];
mtoo = Flatten[mat, 1];
In[81]:= Timing[mft = Partition[
Map[Fourier[#, FourierParameters -> {1, -1}] &, mtoo], 647];]
Out[81]= {1.13, Null}
In[82]:= Timing[mft2 = Partition[mtoo.Transpose[f8mat], 647];]
Out[82]= {0.06, Null}
In[83]:= Max[Abs[mft - mft2]]
Out[83]= 1.43214*10^-14
Daniel Lichtblau
Wolfram Research
- References:
- FFT Speed
- From: to <todummy@gmail.com>
- FFT Speed