Re: FFT proposal for gsoc 2021

From: Janek Kozicki (janek.listy.mailowe_at_[hidden])
Date: 2021-03-11 17:35:16

Hello,

Eduardo Quintana via Boost said:     (by the date of Thu, 11 Mar 2021 09:46:58 +0000)
> I've been working on a C++ templated library for Fast Fourier Transforms,
> https://github.com/Lagrang3/fftx.
> Templated because some FFT algorithms are algebraic-field independent, eg. you
> could FFT an array of N matrices provided a Nth matrix-root-of-unity is given.
> As a result you could have a single algorithm for a variety of underlying, eg.
> `std::complex<float>`, `std::complex<double>`, `std::complex<long double>`,
> `boost::math::quaternion`, finite field types (this would yield the
> "Number theoretic transform" https://cp-algorithms.com/algebra/fft.html#toc-tgt-6 ).

(above this link does not work for me)
 
> I would like to improve this library during the GSOC 2021, as a proposal for
> inclusion inside Boost.Math or Boost.Algorithms.
> 
> Is there anyone interested in supervising this project? Any opinions?

This was recommended here as a topic for GSOC:

https://github.com/boostorg/math/issues/303#issuecomment-573828731
https://github.com/boostorg/math/issues/303#issuecomment-583140413

So definitely a good idea. I am interested in this project. I might
help with mentoring (I know FFT math and C++14/17 inside-out),
but I cannot be a mentor because I don't know boost library
inside-out. So I can help with technical coding aspects, but a real
mentor has to tell where a specific feature has to go into boost library.

Now I have looked at the code at https://github.com/Lagrang3/fftx

1. It is good that you also provide a wrapper for fftw and OpenMP fftw,
   such wrapper is missing in boost.

2. Isn't there prime factorization somewhere in boost? you do this manually.

3. you are working with std::vector storage, but I think that you
   should use boost::ublas::tensor 

Your code looks quite modern, it is definitely a short sketch, not a
complete library, nothing spectacular.

The first thing to do will be to cut corners. The FFT topic is huge,
and GSOC time is limited. Better to do a bit less, but to do it well.
Maybe for example a well written wrapper for libfftw with C++
metaprogramming slots ready to enable full number theoretic transform
at a later stage. Or something similar.

So to summarize: I am interested. I have never took part in GSOC on
either side, so I have no idea how this stuff is organized. I can
help with theoretical mathematical and with technical C++ 14/17/20
aspects. But I don't know boost library well enough, where what types
are defined, etc. Someone else has to take good care of these things
if mentoring. My time is limited, but if others will pick it up,
I will do my best.

best regards
Janek Kozicki

--
Janek Kozicki, PhD. DSc. Arch. Assoc. Prof.
Gdañsk University of Technology
Faculty of Applied Physics and Mathematics
Department of Theoretical Physics and Quantum Information
--
http://yade-dem.org/
http://pg.edu.pl/jkozicki (click English flag on top right)