[PYTHON MATRIX-SIG] 2D fft

[James Crotinger]

Jim Hugunin writes:
 > 
 > I've been looking into providing a 2d fft routine in the standard library
 > and noticed that matlab uses the following to get a 2d fft given a 1d fft
 > routine (with broadcasting).  Does anybody who knows more about this care
 > to comment (horribly inaccurate/inefficient)?  Otherwise I'll use roughly
 > this code in the standard library:
 > 
 > def fft2d(x):
 > 	return fft(fft(x, axis=-1), axis=-2)
 > 

  Correct - the 2D fft kernal is just the product of the 1D kernals
because exp(a x + b y) = exp(a x) * exp(b y).

  However, doing this in the above manner is not necessarily the most
efficient. Most multidimensional FFT routines put the innermost loop
over the number of vectors being transformed. This is done because the
1D fft algorithm has a rather complicated memory access pattern, and,
at least on vector machines, you get a huge speedup by vectorizing in
the other direction(s). On RISC workstations things are considerably
less clear, depending on cache size versus problem size, etc.

  Jim



=================
MATRIX-SIG  - SIG on Matrix Math for Python

send messages to: matrix-sig@python.org
administrivia to: matrix-sig-request@python.org
=================