Changes between Version 22 and Version 23 of Examples/Fft2dHighpass


Ignore:
Timestamp:
May 17, 2010, 8:28:27 AM (10 years ago)
Author:
benl
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Examples/Fft2dHighpass

    v22 v23  
    4848The 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 intermediate data is written into new vectors at each recursion. A 512 point FFT is built from two 256 point FFTs, which are built 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. The base case is a 2 point vector, so there are 256 of them to allocate then unbox at the lowest step.
    4949
    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.
     50Jones's version also uses a 1d radix-2 DIT FFT kernel, but it first reorders the values then performs an 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.
    5151
    5252FFTW contains deep magic, and is comparable with vendor optimised versions.