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


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

Re: FFT Speed

Started byDaniel Lichtblau <danl@wolfram.com>
First post2011-10-08 18:40 +0000
Last post2011-10-11 08:23 +0000
Articles 2 — 2 participants

Back to article view | Back to comp.soft-sys.math.mathematica

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.


Contents

  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

#5518 — Re: FFT Speed

FromDaniel Lichtblau <danl@wolfram.com>
Date2011-10-08 18:40 +0000
SubjectRe: FFT Speed
Message-ID<j6q5ea$otp$1@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

[toc] | [next] | [standalone]


#5583

Fromto <todummy@gmail.com>
Date2011-10-11 08:23 +0000
Message-ID<j70ue7$on$1@smc.vnet.net>
In reply to#5518
Daniel,

Thank you for the suggestion to implement the definition of FFT
myself.  The way mathematica works behind the scene still remains a
mystery to me.  The 3D array was stored as a packed array in my
original code, so I expected that this would suppress any type
checking mathematica might do before processing and hence limit the
overhead.

Regards,

Peter

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web