Re: [boost] fft

From: Ralf W. Grosse-Kunstleve (rwgk_at_[hidden])
Date: 2002-09-23 17:29:13

Cross-posted to the boost list and the Python C++ SIG.

--- Jason D Schmidt <jd.schmidt_at_[hidden]> wrote:
> Think about this:
> 
> a = fft(b);        // a is complex, b could be either real or complex
>                       // easy to do, just overload the function
> 
> fft(b);             // b could either real or complex
>                      // however the ft of real input MUST be a real
> result
> 
> I think the most common use of the ft is to transform real data, which
> returns a complex result (in general).

A generic, pure C++ FFT library derived from FFTPACK is available in
this CVS tree:

cvs -d:pserver:anonymous_at_[hidden]:/cvsroot/cctbx co scitbx

The FFT code is fully documented:

scitbx/include/scitbx/fftpack/*.h

The boost header files are required.

Using scitbx as a pure C++ library does /not/ require a compiled
support library.

On a recent RedHat system it should be possible to run the two commands
below to get boost, scitbx, scons and then compile the regression tests
and the Boost.Python (Version 2) bindings for everything.

wget http://cci.lbl.gov/~rwgk/scitbx/cold_start_redhat_73_csh
csh cold_start_redhat_73_csh

It was quite tricky to work out a nice method for handling the in-place
real-to-complex transforms. I ended up writing an entire "array_family"
to support this (and many other things). I hope to have documentation
for the array_family before the end of the year. Until then, the
regression tests (scitbx/fftpack/timing/*.cpp,
scitbx/array_family/tst_*.cpp) and the code for the Python bindings
(scitbx/fftpack/boost_python/*.cpp) can be used as examples.

FFTW is a truly amazing library and it will require years of effort to
develop a serious competition. One possible way to work around the
restrictive (GPL) FFTW license is to use scitbx/fftpack as a "generic"
solution. If SCons finds a certain environmental variable it uses FFTW
for the 1D transforms, and scitbx/fftpack otherwise (for a proof of
concept search for FFTW_BUILD in scitbx/fftpack/timing SConscript).
This will work particularly well if the FFT library is used mainly
from Python.

I view FFTW's restriction to one floating point type per running
process as a serious limitation only for ND transforms since the arrays
involved are potentially huge. Here I see the biggest opportunity for
generic programming to make a difference sooner rather than later:

Inspection of FFTW's ND-array transforms shows that sophisticated
buffering is used to achieve maximum runtime performance. Therefore a
C++ ND transform interface could be templated on the floating point
type of the ND arrays but (if FFTW is to be used for the underlying 1D
transforms) the implementation would always use buffers of a certain type
(double). This could be hidden from the user and will most likely involve
only a negligible runtime penalty compared to a hypothetical FFT library
with generic 1D transforms that compares favorably with FFTW.

scitbx is unrestricted open source. Contributions are most welcome.
I'd support moving parts over to boost as much as my time permits,
if anyone is interested in getting a fast start that way.

Ralf

P.S.:

The cold_start command checks out the /most current/ CVS trees, so I am
taking my chances here. It worked great an hour ago (using the
SourceForge compile farm),

Depending on the speed of the CPU, compilation will take a while
(10-30 minutes). Note that almost all the time is spent at compiling
the Python bindings, in particular the bindings for the array_family.

cold_start_redhat_73_csh requirements:
  python2 == python 2.2 or higher (default on RedHat 7.3)
  g++ == 2.96 or higher (default on RedHat 7.3)

__________________________________________________
Do you Yahoo!?
New DSL Internet Access from SBC & Yahoo!
http://sbc.yahoo.com