
Boost : 
From: Eduardo Quintana (eduardo.quintana_at_[hidden])
Date: 20210403 06:50:45
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 complexDFT. 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_{ij}
produces, in my opinion, many questions to the reader for instance:
what do we do with the negative indexes? Zeropad 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 CooleyTukey and mixedradix,
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 backends: mine for general
purposes DFTs and FFTW for complex DFTs. My backend is halfway through I have
implemented:
 two versions of the mixedradix CooleyTukes (aka GoodThomas)
recursively and not,
 a pure CooleyTukey inplace which is the one in the blue
line shown here: https://github.com/Lagrang3/fftx/blob/master/assets/powers2.png
That makes the backend functional for any DFT size, with the inconvenience of
the O(n^2) slowdown 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 backend is that I can test its
performance against other complexDFT (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
> 3dimensional 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk