Changes between Version 15 and Version 16 of Examples/Fft2dHighpass
- Timestamp:
- May 17, 2010, 8:20:03 AM (14 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Examples/Fft2dHighpass
v15 v16 46 46 || Using FFTW using Estimate mode || 0.09 || [http://code.haskell.org/repa/repa-head/repa-examples/FFT/HighPass/legacy/c/FFTW.c FFTW.c] || 47 47 48 The vector version uses the same recursive radix-2 decimation in time (DIT) algorithm as the Repa version, but is not rank generalised. It applies a recursive 1d FFT to each row and then transposes the matrix, twice . Recursive FFT algorithms tend to be slower than in-place ones because the data is copied into new vectors at each recursion. A 512 point FFT is built from two 256 point FFTs, which are build from 4 128 point FFTs and so on. The result of each FFT is a new vector which needs to be allocated and then filled.48 The vector version uses the same recursive radix-2 decimation in time (DIT) algorithm as the Repa version, but is not rank generalised. It applies a recursive 1d FFT to each row and then transposes the matrix, twice each. Recursive FFT algorithms tend to be slower than in-place ones because the data is copied into new vectors at each recursion. A 512 point FFT is built from two 256 point FFTs, which are build from 4 128 point FFTs and so on. The result of each FFT is a new vector which needs to be allocated, filled, then unboxed again during the next recursion. 49 49 50 Jones's version also uses a 1d radix-2 DIT FFT kernel, but it first reorders the values then performs a in-place transform using three nested loops. 50 Jones's version also uses a 1d radix-2 DIT FFT kernel, but it first reorders the values then performs a in-place transform using three nested loops. Using an in-place algorithm gives better locality, and avoids the need to allocate and unbox all the intermediate vectors. 51 51 52 52 FFTW contains deep magic, and is comparable with vendor optimised versions.