Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #5518
| 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> |
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
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