Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #5518 > unrolled thread
| Started by | Daniel Lichtblau <danl@wolfram.com> |
|---|---|
| First post | 2011-10-08 18:40 +0000 |
| Last post | 2011-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.
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
| From | Daniel Lichtblau <danl@wolfram.com> |
|---|---|
| Date | 2011-10-08 18:40 +0000 |
| Subject | Re: 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]
| From | to <todummy@gmail.com> |
|---|---|
| Date | 2011-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