2
$\begingroup$

After brief intro to Fourier series, CFT, DFT and their basic properties I enjoyed implementing forward and backward FFT algorithm in complex numbers. I was happy to, at least, have an idea how is it possible that the algorithm works :)

But! My objective is to implement fast integer multiplication algorithm so I began to study The Schönhage–Strassen algorithm (well written here, page 56 of the book/page 72 of the pdf). Also in some other papers I found reference to weighting. And this is what bothers me now.

Why do we need to weight the polynomial coeficients ($a_j$ and $b_j$) with $\theta^j$ before the transformations and unweight the convoluted coeficients ($c_j$) with $K\theta^j$?

There was no weighting function in complex FFT. 'Only' a normalization factor $1/2$ in the backward FFT. I think I've missed some important point :(

I also wonder if the SSA algorithm presendet by Brent & Zimmermann is better/faster/more efficient than algorithm presented here (the approach suggested by Schönhage and Strassen).

$\endgroup$
1
  • 1
    $\begingroup$ @MartinBerger: For your information in view of your edit-summary, umlauts in titles work in principle, but html-entities are escaped, so one cannot enter them in this way (which from the usage in the body I assume was what you tried). $\endgroup$
    – user9072
    Jul 19, 2013 at 12:19

2 Answers 2

1
$\begingroup$

I don't have a direct answer for your question, but you might like the book H.J. Nussbaumer: Fast Fourier Transform and Convolution Algorithms. Published 1981, 2nd Edition 1982, Springer-Verlag. It has a lot of material about finite-field FFT's and so-called number-theoretic transforms. It may be out of date by now, but I remember finding it interesting when I was looking into this subject a while back.

$\endgroup$
1
$\begingroup$

You could double check with Modern Computer Algebra, p.238 - I believe the factors $\theta^j$ are evolving by adjoining "virtual" roots of unity, so that we compute a DFT in $R[x]/\langle x^n+1\rangle$ instead in $R[x]/\langle x^n - 1\rangle$. This is also the content of remark 2 in Modern Computer Arithmetic.

SSA isn't really a DFT - for a DFT you would need a principal root of unity. While DFT multiplication is based on cyclic convolution, SSA uses a negative wrapped convolution.

The algorithm 2.4 in Brent & Zimmermann is a SSA.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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