3
$\begingroup$

I am doing FFT-based multiplication of polynomials with integer coefficients (long integers, in fact). The coefficients have a maximum value of $BASE-1, \quad BASE \in \mathbb{n},\quad BASE > 1$.

I would like to put forward a formal argument that if we use complex DFT for computing a convolution on a physical machine, it will yield incorrect results at some transform length $n\in \mathbb{N}$.

What was easy to prove was the fact that at some big $n$ computing the convolution with DFT will not at all be possible, since, for example, the following difference of primitive roots modulo $n$: $\omega_n^1 - \omega_n^2 \rightarrow 0$ when $n \rightarrow \infty$, and if we are restricted by some machine epsilon $\epsilon$, at some $n$ it will make the values indistinguishable and interpolation impossible.

But the boundary I've received using such an argument was way too big: only for $n=2^{60}$ I've received $\omega_n^1 - \omega_n^2$ that had both components, $Re$ and $Im$, less than representable by $double$-precision type. This certainly is a boundary, but not very practical one.

What I would like to show (if it is possible), is that much earlier than interpolation becomes theoretically impossible, the round-off errors will start to give wrong coefficients in the convolution, so that

$$a\cdot b \neq IDFT(DFT(a)\times DFT(b)),$$

where $DFT$ and $IDFT$ are algorithm implementations that I use to calculate the Fourier transform.

Maybe it is possible to make use of the fact that the value of the primitive root modulo $n$, $\omega_n = \exp(-2\pi i / n)$, is an irrational number for the majority of $n$'s. It will thereby be computed with inevitable error $\psi$, defined as the value needed to "round off" everything that's less than the machine epsilon $\epsilon$. Thus all the values used for DFT,

$$\omega_n^0, \omega_n^1, ..., \omega_n^{n-1},$$

except for $\omega_n^0$ will also be computed with errors.

Since I'm not a good mathematician at all, I don't know if and how I could use this fact to prove that the situation is going to worsen with increasing $n$ and that eventually the convolution is going to be computed incorrectly.

I would also like to have and argument for OR against the following claim: for fixed $n$, the maximal error will be produced when all the coefficients of both polynomials are $BASE-1$.

Thank you very much in advance!

$\endgroup$
  • 1
    $\begingroup$ I don't know what "FFT" and "DFT" are. You might want to edit links to explanations in; but then, those who can answer probably know what you refer to. $\endgroup$ – Raphael May 14 '12 at 15:44
  • $\begingroup$ fast fourier transform and discrete fourier transform (FFT is an algorithm to compute DFT of a function, although people often conflate the two) $\endgroup$ – Sasho Nikolov May 14 '12 at 15:55
2
$\begingroup$

Since the fourier coefficients might in general be complex numbers $xi + y$ with $x$ or $y$ or both irrational, a standard finite precision computer of course will not output the exact fourier coefficients. However, if you want to claim that you cannot get a good approximation, you are wrong.

Look at this answer. Markus shows that if you want to compute DFT of a vector of length $n$ up to $b$ bits of precision, then you need floating point numbers with $m$ bits where $m = \log n + \log \log n + b + C$ for $C$ some fixed constant. This is a fairly good bound. Also, there is no reason why the double type of the C language should be any hard limitation if you care about precision: there are libraries for high-precision arithmethic, and it's not even all that hard to code your own procedures to multiply and add floating point numbers of fixed high (higher than that of double) precision. Markus's answer shows that you won't lose much in running time: the running time will be roughly $n \log n (b/\log n)$ (for $b > \log n$) arithmetic operations on standard C types.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.