**Polynomial multiplication**

Given two degree polynomials and , compute where .

**Naive approach**: Computing takes steps and there are steps, hence it would take time. Using the divide and conquer approach from the integer multiplication algorithm would give us a running time of . (Assume multiplying integers takes steps). Can we do better?

**Fact**: A degree polynomial is uniquely characterized by its values at any distinct points.

**Idea**: Suppose we were given and evaluated at distinct points and wanted evaluated at the same points, then we could compute it in time by simply returning . Thus an alternative approach would be:

- Choose distinct points and evaluate and on those points
- Compute
- Compute from .

Notice that since and are of degree , has degree at most and so by the above fact uniquely fixes . Clearly the second step takes time. Hence it remains to address the complexity of the first and third steps. The first step is called *evaluation *and the third step is called *interpolation*. Note also that we are free to choose any as long as they are distinct.

**Evaluation**

Given a polynomial of degree we wish to evaluate it at . Clearly one can do it in time by evaluating each serially. Can we do it faster?

For general we cannot; however a clever choice of ‘s can help. For example if our points were of the form then we could write as , where the degree of is at most . Suppose we wish to evaluate on and . We have and . Thus in order to evaluate on it suffices to evaluate on . Note that we reduced our problem of evaluating a degree polynomial on points to the problem of evaluating two degree polynomials on points. If we could ensure that are also of this special form then we could keep doing this trick further.

**Choosing the points**: Suppose we choose our points to be where is a primitive root of unity, i.e. . If is even then

- is a primitive root of unity.

Notice that if is a power of then the two properties ensure that the above trick works. Property ensures that can be written as . Property ensures that we can keep doing this since is a primitive root of unity.

This gives us the following algorithm for evaluating on .

- If return
- Let
- Recursively compute by calling .
- Recursively compute by calling .
- For to , compute as .
- Return .

If is the time to evaluate a degree polynomial on then we get implying .

**Interpolation**

Given we wish to compute . Notice that for any we have

One can show that if the ‘s are distinct then this matrix is invertible. Let be this matrix where . This matrix is called the *Van der Monde matrix*. It has the following nice property: .

In other words to compute one needs to evaluate the polynomial at , where . Observe that is also a primitive root of unity. But we already know how to solve this problem! Thus interpolation is equivalent to evaluation and has time complexity .

Combining the time complexity of the three steps gives us a algorithm to multiply two polynomials of degree .

Could you post the exams for practice purposes?

No we will not be posting the exam on the website.

Will this topic be on the test?

No. The test covers Lecture material from Jan 26th to Feb 9th (graph search, greedy)