Fast Fourier Transformation and its Application in Polynomial Multiplication

Table of Contents

• Introduction
• Idea of using FFT for polynomial multiplication
• Divide and Conquer Algorithm
• Inverse Discrete Fourier Transform
• Fast Polynomial Multiplication
• Algorithm
• Conclusion
• References

Introduction

The Fast Fourier Transformation (FFT) is an algorithm for computing the discrete Fourier transform (DFT) of a sequence. The DFT is a mathematical operation that converts a sequence of numbers into a sequence of frequencies. The FFT is a very efficient algorithm, and it can be used to solve a variety of problems, including polynomial multiplication.

The naive algorithm for multiplying two polynomials of degree n requires O(n^2) operations. This is because the naive algorithm multiplies each coefficient of the first polynomial with each coefficient of the second polynomial. The FFT can be used to improve the time complexity of polynomial multiplication to O(nlogn).

Idea of using FFT for polynomial multiplication

First, consider the different representations of polynomials, and the time necessary to complete polynomial multiplication based on the representation. There are 3 main representations to consider.

1. Coefficient vector: This representation involves listing the coefficients of the polynomial, starting from the highest power of x down to the lowest power. For example, if we have a polynomial 3x^2 + 2x + 1, the coefficient vector representation would be [3, 2, 1]. Operations like addition, subtraction, and multiplication can be done by simply manipulating these coefficient vectors. Evaluating the polynomial at a specific value of x can be done relatively quickly.
2. Roots: In this representation, we express the polynomial in terms of its roots (the values of x that make the polynomial equal to zero) and a scale term. For example, if we have a polynomial (x - 1)(x - 2)(x - 3), we can represent it as (x - r0)(x - r1)(x - r2) multiplied by a constant term c. However, finding the exact roots of a polynomial can be difficult or even impossible using basic arithmetic operations. Multiplication is relatively straightforward, as it involves concatenating the roots. Evaluating the polynomial at a specific value of x can be done in a reasonable amount of time.
3. Samples: This representation involves using a set of sample points that lie on the polynomial curve. Each sample point consists of an x-coordinate and a corresponding y-coordinate. For example, we might have sample points (1, 2), (2, 5), and (3, 10) for a quadratic polynomial. These sample points uniquely determine the polynomial according to certain mathematical theorems. Addition and multiplication can be computed by adding and multiplying the y-coordinates, assuming the x-coordinates match. However, evaluating the polynomial at a specific value of x requires interpolation, which takes more time.

The idea behind using the FFT for polynomial multiplication is to represent the polynomials in a different way. Instead of representing the polynomials as sequences of coefficients, we represent them as sequences of values. The values are the polynomials evaluated at a set of special points called the roots of unity.

The DFT can be used to efficiently compute the sequences of values for the two polynomials. Once we have the sequences of values, we can multiply them together using a simple algorithm. The product of the two sequences of values is the sequence of values for the product of the two polynomials.

Finally, we can use the inverse DFT to convert the sequence of values for the product polynomial back into a sequence of coefficients. The coefficients of the product polynomial are the product of the original two polynomials.

The FFT is a powerful algorithm that can be used to solve a variety of problems. In the case of polynomial multiplication, the FFT can be used to improve the time complexity from O(n^2) to O(nlogn). This is a significant improvement, and it makes polynomial multiplication a much more efficient operation.

Divide and Conquer Algorithm

To multiply two polynomials efficiently, we can use a divide and conquer algorithm. Here are the steps:

• Divide the polynomial into even and odd coefficients.
  • Separate the even-indexed coefficients (a0, a2, a4, ...) into one polynomial, Aeven(x).
  • Separate the odd-indexed coefficients (a1, a3, a5, ...) into another polynomial, Aodd(x).
• Recursively multiply Aeven(y) and Aodd(y) for smaller values of y.
  • Apply the same algorithm to the polynomials Aeven and Aodd, but with a reduced set of values for x.
  • Repeat this process until we reach a base case where the polynomial has only one coefficient.
• Combine the results of the even and odd terms.
  • Add the results of multiplying Aeven(x2) and x times Aodd(x2), where x2 represents the reduced set of values.
  • This step combines the terms to obtain the final result, A(x).

However, if the polynomial size and the set of values, X, are not collapsing (shrinking), the time complexity of this algorithm remains the same as the traditional approach, which is O(n^2). To achieve better efficiency, the set of values, X, should collapse recursively, such that either X has only one value (base case) or the reduced set X2 has the same size as X and is collapsing recursively. In such cases, the time complexity becomes O(n log n), which is much faster than the previous approach.

Inverse Discrete Fourier Transform

The Inverse Discrete Fourier Transform is an algorithm to return the coefficients of a polynomial from the multiplied samples. The transformation is of the form A∗ → V^−1 · A∗ = A. In order to compute this, we need to find V^−1, which in fact has a very nice structure.

The Inverse Discrete Fourier Transform is equivalent to the Discrete Fourier Transform, but changing xk from e^ikτ/n to its complex conjugate e^−ikτ/n, and dividing the resulting vector by n. The algorithm for IFFT is analogous to that for FFT, and the result is an O(nlog n) algorithm for IDFT.

Fast Polynomial Multiplication

In order to compute the product of two polynomials A and B, we can perform the following steps:

1. Compute A* = FFT (A) and B* = FFT* (B), which converts both A* and B* from coefficient vectors to a sample representation.
2. Compute C*= A* . B* in sample representation in linear time by calculating Ck = Ak · Bk (∀k).
3. Compute C* = IFFT(C*), which is a vector representation of our final solution.

Algorithm

Here is the C++ implementation:

#include <bits/stdc++.h>

typedef std::complex<double> Complex;
typedef std::vector<Complex> ComplexVector;

void fft(ComplexVector& input, bool inverse = false) {
    const int n = input.size();
    if (n <= 1) {
        return;
    }

    ComplexVector even(n / 2);
    ComplexVector odd(n / 2);

    for (int i = 0; 2 * i < n; ++i) {
        even[i] = input[2 * i];
        odd[i] = input[2 * i + 1];
    }

    fft(even, inverse);
    fft(odd, inverse);

    const double angle = 2 * M_PI / n * (inverse ? -1 : 1);
    Complex w(1);
    Complex wn(std::cos(angle), std::sin(angle));

    for (int k = 0; 2 * k < n; ++k) {
        input[k] = even[k] + w * odd[k];
        input[k + n / 2] = even[k] - w * odd[k];
        if (inverse) {
            input[k] /= 2;
            input[k + n / 2] /= 2;
        }
        w *= wn;
    }
}

ComplexVector polynomialMultiplication(const ComplexVector& a, const ComplexVector &b) {

    int n = 1;
    while (n < a.size() + b.size() - 1) {
        n <<= 1;
    }

    ComplexVector fa(a.begin(), a.end());
    ComplexVector fb(b.begin(), b.end());

    fa.resize(n);
    fb.resize(n);
    
    fft(fa);
    fft(fb);
    
    for (int i = 0; i < n; ++i) {
        fa[i] *= fb[i];
    }

    fft(fa, true);
    return fa;

}

Conclusion

The Fast Fourier Transformation (FFT) algorithm provides an efficient method for computing the Discrete Fourier Transform and its inverse. By exploiting the symmetry properties and periodicity of complex roots of unity, the FFT algorithm reduces the time complexity from O(n^2) to O(n log n), where n is the size of the input sequence.

One of the key applications of the FFT algorithm is in polynomial multiplication. By converting polynomials to the frequency domain using FFT, the multiplication operation can be performed efficiently as a convolution operation in the frequency domain. This approach significantly improves the time complexity of polynomial multiplication from O(n^2) to O(n log n), making it a valuable technique in various applications that involve polynomial manipulations.

References

MIT OCW Lecture Video

MIT OCW Lecture Note