Re: FFT proposal for gsoc 2021

From: Eduardo Quintana (eduardo.quintana_at_[hidden])
Date: 2021-04-03 06:50:45

 ('
' encoding is not supported, stored as-is)
Hi Kostas,

Good critics are necessary for the sake of improvement.
All of your comments are welcome.

> 1) The discussion of NTT. While boost.multiprecision can potentially be used
> to implement the Zp ring, it currently does not contain any such construct.
> Reading further, there is nothing about NTT in the deliverables.  If the idea
> is peripheral to the GSOC project, then it does not need to be mentioned at
> all.  Note that even the  PARI library does not yet have NTT implemented and
> for them I think it is a high priority (must be a very hard problem).

1) I mentioned the NTT because is part of the motivation for having a general
DFT instead just complex-DFT. Maybe the text it is not clear. You'll get the NTT
for free.
See these two examples
https://github.com/Lagrang3/fftx/blob/master/examples/ex02.cpp
https://github.com/Lagrang3/fftx/blob/master/examples/ex03.cpp

Unfortunately I haven't produced a convolution routine yet, hence in ex03 I had
to compute it explicitely. There is also a small implementation of Zp
https://github.com/Lagrang3/fftx/blob/master/examples/modulo.h
if there was one in Boost I would gladly use it.

> 2) Section 2.2. Most people know the Convolution Theorem, but at least myself
> do not know anything about the Rader algorithm.  Since you propose to
> implement it, why not describe it in that Section, maybe instead of the
> Convolution Theorem.

2) The Convolution Theorem is very well known yes. I wanted just to make a small
subsection in order to clarify which flavour of the Convolution I am using:
the Circular Discrete Convolution (CDC) which fits naturally into the DFT scheme.
The other Discrete Convolution is the one that you write as
c_i = \sum_{j} a_j b_{i-j}
produces, in my opinion, many questions to the reader for instance:
what do we do with the negative indexes? Zero-pad them or wrap around from the
end?

I think writing proofs and detailed algorithms is not necessary for the text of
the proposal. Last year when I started the fftx experiment I came to the
conclusion at some point that I needed, besides Cooley-Tukey and mixed-radix,
another algorithm to compute the DFT for prime sizes.
Then I found the description of Rader's algorithm in Wikipedia.
FFTW uses it, by the way.

> 3) Section 2.3. You say: "FFTW was designed to compute DFT for complex
> numbers, like in Example 1.  There is no support for DFT in the broader sense
> of Definition 1. For example, we cannot use FFTW to compute the NTTs described
> in the Example 2." Since you are not going to be able to solve this problem in
> this GSOC project, it is better to not make such comments.

3) Yes I will solve that problem. There will be two back-ends: mine for general
purposes DFTs and FFTW for complex DFTs. My back-end is half-way through I have
implemented:
- two versions of the mixed-radix Cooley-Tukes (aka Good-Thomas)
recursively and not,
- a pure Cooley-Tukey in-place which is the one in the blue
line shown here: https://github.com/Lagrang3/fftx/blob/master/assets/powers-2.png
That makes the back-end functional for any DFT size, with the inconvenience of
the O(n^2) slow-down for prime numbers.
The work to be done from now on will include the Rader algorithm (for the prime
case) and further performance improvements.

A funny thing about this general purpose DFT back-end is that I can test its
performance against other complex-DFT (eg. FFTW). If some knows of a NTT library
or the implementation of weirder DFTs to compare with, please raise your hand.

> 4) Section 2.3. "scalability of the parallel MPI routines for computing
> 3-dimensional DFT" , "domain decomposition" - here again I think it is worth
> to remember that if the project is not going to address domain decomposition,
> then it is better to not talk about it.

4) That's true. But that's a very urgent problem that we could very well solve
originally within Boost. However it cannot be done until we produce a Boost FFT.
Hence you get an extra motivation for doing the Boost FFT.

> 5) Since this project is done under Boost, it seems logical to make sure  the
> proposed code work with Boost.Math complex types. Is this not part of the
> plan? Why no word about it in the deliverables?

5) It did cross my mind, but I clearly forgot to talk about it. Thanks for
alerting me.

Thanks for the feedback.
Eduardo