Editing Discrete Fourier transform (section)

===Polynomial multiplication===

Suppose we wish to compute the polynomial product ''c''(''x'') = ''a''(''x'') · ''b''(''x'').  The ordinary product expression for the coefficients of ''c'' involves a linear (acyclic) convolution, where indices do not "wrap around."  This can be rewritten as a cyclic convolution by taking the coefficient vectors for ''a''(''x'') and ''b''(''x'') with constant term first, then appending zeros so that the resultant coefficient vectors '''a''' and '''b''' have dimension {{Nowrap|''d'' > deg(''a''(''x'')) + deg(''b''(''x''))}}.  Then,

:<math>\mathbf{c} = \mathbf{a} * \mathbf{b}</math>

Where '''c''' is the vector of coefficients for ''c''(''x''), and the convolution operator <math>*\,</math> is defined so

:<math>c_n = \sum_{m=0}^{d-1}a_m b_{n-m\ \mathrm{mod}\ d} \qquad\qquad\qquad n=0,1\dots,d-1</math>

But convolution becomes multiplication under the DFT:

:<math>\mathcal{F}(\mathbf{c}) = \mathcal{F}(\mathbf{a})\mathcal{F}(\mathbf{b})</math>

Here the vector product is taken elementwise.  Thus the coefficients of the product polynomial ''c''(''x'') are just the terms 0, ..., deg(''a''(''x'')) + deg(''b''(''x'')) of the coefficient vector

:<math>\mathbf{c} = \mathcal{F}^{-1}(\mathcal{F}(\mathbf{a})\mathcal{F}(\mathbf{b})).</math>

With a [[fast Fourier transform]], the resulting algorithm takes ''O''(''N''&nbsp;log&nbsp;''N'') arithmetic operations.  Due to its simplicity and speed, the [[Cooley–Tukey FFT algorithm]], which is limited to [[composite number|composite]] sizes, is often chosen for the transform operation.  In this case, ''d'' should be chosen as the smallest integer greater than the sum of the input polynomial degrees that is factorizable into small prime factors (e.g. 2, 3, and 5, depending upon the FFT implementation).

====Multiplication of large integers====

The fastest known [[multiplication algorithms|algorithms]] for the multiplication of very large [[integer]]s use the polynomial multiplication method outlined above.  Integers can be treated as the value of a polynomial evaluated specifically at the number base, with the coefficients of the polynomial corresponding to the digits in that base (ex. <math>123 = 1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^0</math>).  After polynomial multiplication, a relatively low-complexity carry-propagation step completes the multiplication.

==== Convolution ====
When data is [[Convolution|convolved]] with a function with wide support, such as for downsampling by a large sampling ratio, because of the [[Convolution theorem]] and the FFT algorithm, it may be faster to transform it, multiply pointwise by the transform of the filter and then reverse transform it.  Alternatively, a good filter is obtained by simply truncating the transformed data and re-transforming the shortened data set.