2
$\begingroup$

The question is how fast we can perform an $n$ coefficient discrete Fourier transform on the log-RAM model of computation. If we assume that we can do arithmetic operations on registers of size $\log{(n)}$ in constant time, we essentially have the log-RAM model explained in Martin Fürer's preprint "How Fast Can We Multiply Large Integers on an Actual Computer?".

So how fast can we perform the DFT in this model? Fürer's paper also notes that Schönhage and Strassen's first algorithm in their seminal paper on integer multiplication runs in time $O(n)$ in this model. Could it be that we can perform the DFT in linear time in this model?

For instance, Bluestein's "A linear filtering approach to the computation of discrete Fourier transform" can help to reduce DFTs to integer multiplication. One can see "Even faster integer multiplication" by Harvey and van der Hoeven for more ideas on this. Again, since integer multiplication can be done in linear time in this model, the DFT may be faster, too.

Is there any advantage to performing a number theoretic transform in this model? This is when all coefficients are nonnegative integers and the transform is done over some finite field $\mathbb{F}_p$, $p$ prime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.