Re: FFT proposal for gsoc 2021

From: Eduardo Quintana (eduardo.quintana_at_[hidden])
Date: 2021-03-31 07:12:08

Hi Kostas,

> 	• Boost
> 	• FFTW
> 	• google/benchmark
> 	• alglib
> 	• meson
> For myself that is too much, so I could not even try your library.
> 
> Q1) Do you plan to get rid of external dependencies other than FFTW?

Q1) This repository is meant for experimentation. The compulsory dependencies
are: Boost and Meson, the rest are just for benchmarks. Meson and Boost are not
even necessary if you are not interested in the tests or installing the library.
The library is header only thus for trying it is enough to use the contents
under the `include` directory.

> 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>? 
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.

FFT algorithms are oblivious of the representation of the complex type (in the
case of DFT on the complex Field). I want to put this statement into practice
following the lesson from the std::complex<> and templated algorithms.
FFTW cannot do that by any means without
compromising performance because it is written in C. Any FFTW wrapper follows
suit. 

> Q3) Is it really within your capabilities to implement the dispatch mechanisms necessary to wrap FFTW into such an API as that one template, FFT_dim<2>?

Q3) The user interface is not final. It is in the GSOC plan to allocate some
time to decide on that issue.

Thanks for the feedback. Very useful.
Eduardo