4b. Polynomial Multiplication

One of the Applications of Divide and Conquer

Algorithmic Perspective

problem: multiplying two polynomials Given two polynomials $A,B$, output their product $C(x)=A(x)B(x)$. Represent a polynomial $C$ in the input or output as a vector of coefficients. In other words, output the coefficients of the product.

If $A,B$ has degree $\le d-1$ then $C$ has degree $\le 2(d-1)$. Size of problem: $d-1$

Naive algorithm:

$$C_k=\sum _{j=0}^k{a}_j{b}_{k-j}$$

Running time: $O(d)$ coefficients to compute, each taking $O(d)$ time. Total: $O(d^2)$. Lower-bound: $\Omega (d)$ for writing down all coefficients of c.
Can we get faster?

Idea 1

Representing a polynomial by giving a set of points e.g. representing a line via two points instead of the line equation. Possible because can recover the polynomial via the set of points, like computing line equation from two points 2 problems:

1. How to quickly evaluate $A,B$ at these points?
2. How to recover coefficients of C from the evaluations?

Takes d + 1 points to characterize a polynomial of d points.

Continuing on problem 1: Given a polynomial $A$ of degree $\le n-1$, evaluate $A$ at $n$ distinct points.

Naive Approach

$$A(x_j)=\sum _{j=0}^{n-1}{a}_j{x}_k^j$$

Each evaluation takes $O(n)$ time. $O(n)$ evaluations. Total $O(n^2)$ time.

Fast Fourier Transform

Write A by separating even and odd powers of $x$. $A_e$ and $A_o$ are polynomials of degree $\le n/2$.

$$\begin{gathered} \begin{array}{c}A(x)=(a_0+a_2{x}^2+...+a_n{x}^n) \\ +x(a_1+a_3{x}^2+...+a_{n-1}{x}^{n-2}) \\ =A_e(x^2)+x{A}_o(x^2)\end{array} \end{gathered}$$

Need to evaluate $A_e,A_o$ at the set of squares of input points. What if we choose $x_0...x_{n-1}$ to come in positive/negative pairs? Can compute $A(x)$ at $n$ points by evaluating $n/2$ points for both $A_e{A}_o$ Recurrence would be:

$$T(n)=2T(n/2)+O(n)$$

But we cannot recurse: all points passed to $A_e,A_o$ are positive (squares); cannot divide into positive negative pairs. However, this is possible with complex numbers. After squaring them, they can still come in positive/negative pairs.

Solution: plot complex numbers in the X-Y plane (polar cords). After squaring,

$$\{1,i,-1,-i\}⟹\{1,-1\}$$

Definition

The $n^{th}$ roots of unity are the numbers $\{1,w,w^2,w^3,...,w^{n-1}\}$ where $w=(1,2\pi /n)$

The set of $n^{th}$ roots of unity

1. come in positive negative pairs
2. Their squares are the ${(n/2)}^{th}$ roots of unity

$⟹$ $n^{th}$ roots of unity have exactly the properties of the special set of numbers With this set of n numbers, we can evaluate $A(x)$ at the chosen points in $O(nlogn)$ time.

Evaluate coefficients into values and interpolate back to coefficient representations

Interpolation To get the final coefficients

$$coefficients=\frac{1}{n}FFT((values,w^{-1}))$$

Using the same FFT algorithm :3