Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #5518

Re: FFT Speed

From Daniel Lichtblau <danl@wolfram.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: FFT Speed
Date 2011-10-08 18:40 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <j6q5ea$otp$1@smc.vnet.net> (permalink)
References <201110070848.EAA07438@smc.vnet.net>

Show all headers | View raw


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

Back to comp.soft-sys.math.mathematica | Previous | Next — Next in thread | Find similar | Unroll thread


Thread

Re: FFT Speed Daniel Lichtblau <danl@wolfram.com> - 2011-10-08 18:40 +0000
  Re: FFT Speed to <todummy@gmail.com> - 2011-10-11 08:23 +0000

csiph-web