Re: FFT proposal for gsoc 2021

From: Stefan Seefeld (stefan_at_[hidden])
Date: 2021-03-31 12:46:17

On 2021-03-31 3:12 a.m., Eduardo Quintana via Boost wrote:
> Hi Kostas,
>
>> Q2) What do plan offering that exceeds FFTW++ capability?
>>
>> In you file fft-2d.cpp, presumably the example use, it is
>>
>>      vector<complex<double>> FA;
>>      FFT_dim<2>(FA.begin(), FA.end(), N, e);
>>
>> This applies your own templated naive implementations of FFT. However,
>> FFTW does not wrap into this API ! You are using the plain old C interface for FFTW.
> Q2) It was mentioned before by Stefan Seefeld that Boost.Math.FFT should provide
> and FFTW wrapper. I think that's exactly what FFTW++ does. If the time frame of
> the GSOC allows it or the urgency to do that overwhelms the rest of my proposal
> then I believe that Boost.Math.FFT could provide a user interface that doesn't
> necessarily mirrors FFTW.
> When it comes to capabilities, consider that FFTW++ (to my knowledge) cannot do
> more than FFTW does, ie. it is limited by the types used internally on the FFTW
> side.
>
> I will have to take a better look at FFTW++ before giving a more educated
> opinion. By looking at the surface of the code, I see that they've built their
> own complex type based on double and it even has arithmetic operations. That's a
> great improvement with respect to FFTW's POD fftw_complex. Yet I don't see why
> they couldn't use std::complex<double>?

I don't know the FFTW++ project (just had a quick glance), but I did 
write another FFTW C++ wrapper many years ago as part of the "OpenVSIP" 
project (https://github.com/stefanseefeld/openvsip).

Invoking FFTW from C++ wrappers simply involves some 
`reinterpret_cast<>` calls to convert between `std::complex<?>` pointers 
and `fftw?_complex`. Not really a big deal. Arguably, adding custom 
complex types in FFTW++ just makes matters worse, as users of that API 
now have two distinct C++ complex types to deal with.

> What if I need to compute a trascendental function of an fftwpp::Complex?
> The standard library provides all kinds of mathematical functions that take
> complex<T> as arguments.
> What if I need to do a FFT on a complex number with extended precision?
>
> The FFTs I am proposing are templated on the type. So that the user is free to
> use std::complex<whathever_Real> or any user defined type for representing
> complex numbers, or even weirder Fields/Rings (see the proposal for details).
> That's a capability that FFTW/++ don't have.

One thing we did in OpenVSIP is to support different data layouts, 
which, depending on your platform, can greatly affect performance. For 
example, you may do FFTs on "interleaved complex" arrays or "split 
complex" arrays.

It is indeed tricky to offer support for a great range of types (value 
types, data layout types, etc.). What we found critical was the ability 
to "dispatch" to suitable backends automatically. And that is where 
modern C++ techniques can indeed make a big difference. Consider using 
template meta-programming to identify whether the data types and layout 
are supported by FFTW, and if so, call that, else call a different 
backend. Then as an end-user I don't have to think about such choices, 
and can simply trust that I get the best performance available.

(More and more computers contain powerful GPUs, so why not anticipate a 
later addition of FFT implementations based on OpenCL or CUDA, for 
example ? Wouldn't it be nice if the FFT API would be able to 
automatically dispatch to that if that would yield better performance ? 
Etc., etc., there are many things left on the table that don't involve 
re-writing FFT kernels from scratch !)

Regards,

Stefan
-- 
       ...ich hab' noch einen Koffer in Berlin...