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