Fast Fourier Transform (FFT): Polynomial Multiplication, Convolution and Signal Processing

Polynomial multiplication, complex roots of unity and signal convolution are the same computation viewed from different directions. The product (1 + 2x)(3 + 4x) is evaluated through a four-point DFT to obtain 3 + 10x + 8x^2; the FFT butterflies and zero-padding explain the calculation and prevent circular wraparound. The signs follow from the intermediate values.

1. What the FFT Computes and Why It Matters

The discrete Fourier transform maps N coefficients or samples to N frequency-domain values; its inverse maps them back. The fast Fourier transform computes the same DFT in O(N log N) time. FFT is an algorithmic method, not a different transform.

The sign convention is:

X_k = sum from j=0 to N-1 of x_j omega^(jk), where omega = exp(-2 pi i/N).

The inverse is x_j = (1/N) sum from k=0 to N-1 of X_k omega^(-jk). For N = 4, omega = -i.

Polynomial multiplication evaluates both polynomials at the same roots, multiplies matching point values, then interpolates. Divide-and-conquer reuses root symmetry. If you want the wider algorithms route around this topic, start from GATE CS Exam Preparation.

2. Polynomial Multiplication Is Coefficient Convolution

Start with an independent schoolbook check. Let A(x) = 1 + 2x, so a = [1, 2], and B(x) = 3 + 4x, so b = [3, 4].

• c_0 = 1*3 = 3

• c_1 = 1*4 + 2*3 = 4 + 6 = 10

• c_2 = 2*4 = 8

Therefore, C(x) = A(x)B(x) = 3 + 10x + 8x^2, or c = [3, 10, 8].

In general, c_k = sum over valid j of a_j b_(k-j). Inputs with n and m coefficients produce n + m - 1 linear-convolution entries. With required length 3, choose the next power-of-two transform length, N = 4, and pad to [1,2,0,0] and [3,4,0,0].

Schoolbook multiplication is quadratic for equally sized dense inputs; FFT's asymptotic advantage appears as inputs grow.

3. Four-Point DFT Multiplication, Worked from Start to Finish

With omega = -i, the four evaluation points are 1, -i, -1, i.

(1 - 2i)(3 - 4i) = 3 - 10i + 8i^2 = -5 - 10i. Its conjugate is (1 + 2i)(3 + 4i) = -5 + 10i.

Now apply the inverse DFT:

• c_0 = [21 + (-5-10i) + 1 + (-5+10i)]/4 = 12/4 = 3

• c_1 = [21 + i(-5-10i) - 1 - i(-5+10i)]/4 = 40/4 = 10

• c_2 = [21 - (-5-10i) + 1 - (-5+10i)]/4 = 32/4 = 8

• c_3 = [21 - i(-5-10i) - 1 + i(-5+10i)]/4 = 0/4 = 0

Trim the padded zero to get [3,10,8]. Agreement with schoolbook multiplication checks correctness.

4. Radix-2 FFT Butterflies and the O(N log N) Recurrence

The radix-2 split separates even and odd indices. For a = [1,2,0,0], the even-indexed vector is [1,0] and the odd-indexed vector is [2,0]. Their two-point DFTs are E = [1,1] and O = [2,2].

Combine them using X_k = E_k + omega^k O_k and X_(k+N/2) = E_k - omega^k O_k. At k = 0, X_0 = 1 + 2 = 3 and X_2 = 1 - 2 = -1. At k = 1, omega = -i, so X_1 = 1 - 2i and X_3 = 1 + 2i.

For b = [3,4,0,0], the smaller transforms are E = [3,3] and O = [4,4]. Combining gives [7, 3-4i, -1, 3+4i], matching the previous section.

The recurrence is T(N) = 2T(N/2) + Theta(N) = Theta(N log N). Its log_2 N levels each require Theta(N) combination work. For N = 8, the levels are 8 -> 4 -> 2 -> 1. Exact operation counts depend on the implementation.

5. Signal Processing Connection: Linear and Circular Convolution

Read the same inputs as a signal x = [1,2] and a finite impulse response h = [3,4]. Linear convolution gives y[0] = 1*3 = 3, y[1] = 1*4 + 2*3 = 10, and y[2] = 2*4 = 8. These are exactly the polynomial coefficients.

Without padding, a two-point DFT computes two-point circular convolution. The lag-2 value wraps to index 0, so y_circ[0] = 3 + 8 = 11 and y_circ[1] = 10. The result is [11,10], not [3,10,8].

Padding both sequences to at least 2 + 2 - 1 = 3 positions prevents that aliasing. We use N = 4, so DFT multiplication produces [3,10,8,0], which we trim to length 3. Practical frequency-domain filtering uses this same relationship between pointwise multiplication and convolution.

6. A Reliable Implementation Recipe, Numerical Error and Exact Variants

Use this seven-step recipe:

1. Compute the required length L = n + m - 1.

2. Choose a supported transform length N >= L.

3. Zero-pad both vectors to N.

4. Compute two forward FFTs.

5. Multiply matching frequency bins.

6. Apply the inverse FFT and divide according to the chosen convention.

7. Round when exact integral output is expected, then trim to L.

Check another case: P = [2,1,3] and Q = [1,-2,0,4]. Here L = 3 + 4 - 1 = 6, so radix-2 code uses N = 8. Schoolbook convolution gives [2,-3,1,2,4,12]. An FFT implementation must return those six values after justified rounding and trimming.

Floating-point output may contain harmless noise, such as 7.999999999 instead of 8. Use tolerance-aware rounding only when integer coefficients are expected. For exact modular integer arithmetic, a number-theoretic transform is an alternative when compatible moduli are available.

7. Common FFT Traps and How Exam-Style Questions Test Them

• DFT versus FFT: the DFT is the transform; an FFT computes it efficiently.

• Wrong output length: use coefficient counts, L = n + m - 1.

• No zero-padding: linear convolution becomes circular convolution.

• Mixed signs: changing the forward root sign requires a matching inverse convention.

• Missing scale: the inverse here includes 1/N.

• Wrong multiplication: multiply frequency bins, not corresponding input coefficients.

• Untrimmed output: remove coefficients introduced only by padding.

Exam-style exercises ask you to calculate a four-point DFT, complete a butterfly stage, choose a padding length, recover coefficients, or distinguish linear and circular convolution. The official GATE 2026 Computer Science syllabus lists divide-and-conquer under Algorithms but does not explicitly list FFT, so check the current syllabus before you plan your revision.

For timed practice across the algorithms syllabus, use the GATE Test Series: Mocks and Topic-wise Tests. The earlier Algebraic Computation: Polynomial Multiplication, DFT and Strassen's Algorithm owns the broader comparison of algebraic representations, including Strassen and a DFT-matrix pipeline. This post stays with FFT mechanics: radix-2 butterflies, linear versus circular convolution, padding, numerical error and exact variants.

8. FFT Polynomial Multiplication: The Short Version and Next Step

Convert coefficients to padded vectors. FFT both vectors. Multiply matching frequency bins. Apply the inverse FFT, round where justified, and trim. In our example, (1+2x)(3+4x) = 3+10x+8x^2, while the transform product is [21,-5-10i,1,-5+10i].

Now hide Sections 3 and 4, rebuild both four-point transforms, and recover all four inverse outputs by hand. For a broader structured subject route after that exercise, use GATE Guidance by Sanchit Sir.