Roots of Polynomials: Finding Roots and Algorithms

Roots of Polynomials

• The problem is to find all roots of a polynomial $p(x)$ of degree $n$.
• The Fundamental Theorem of Algebra states that every polynomial of degree $n$ has $n$ complex roots.
• There is no closed-form formula for polynomials of degree $\geq 5$.
• Algorithm involves finding one root $z_1$ of $p(x)$, then dividing $p(x)$ by $(x - z_1)$ to get $q(x)$, then recursively finding the roots of $q(x)$.

Finding One Root

• All roots are assumed to be simple.
• Newton's method involves iterating $x_{i+1} = x_i - \frac{p(x_i)}{p'(x_i)}$.
• $x_i$ may converge to some $z_j$ depending on the choice of $x_0$.
• If $|p(x_i)| < \epsilon$, then $x_i$ approximates a root.
• Issue is determining which $x_0$ to choose, and trying multiple random $x_0$ may not guarantee finding all roots.

Smoothed Analysis

• Involves perturbing the polynomial $p(x)$ by a small random polynomial and finding a root of the perturbed polynomial.
• Perturbing is repeated.

Algorithm

• $p(x) = \sum_{i=0}^n a_i x^i$
• $\tilde{p}(x) = p(x) + \sum_{i=0}^n \delta_i x^i$, where $\delta_i \sim N(0, \sigma^2)$ are i.i.d.
• Newton's method is run on $\tilde{p}(x)$ with a random starting point.
• Steps repeated $T$ times
• All roots found are returned
• With high probability, the algorithm finds all roots of $p(x)$ in time $poly(n, \frac{1}{\sigma})$.

Polynomial Interpolation

• Given $n+1$ points $(x_0, y_0), \dots, (x_n, y_n)$ with $x_i \neq x_j$ for $i \neq j$, the problem is to find a polynomial $p(x)$ of degree at most $n$ such that $p(x_i) = y_i$ for all $i$.
• There exists a unique polynomial $p(x)$ of degree at most $n$ such that $p(x_i) = y_i$ for all $i$.

Proof of Existence Using Lagrange Interpolation

• $p(x) = \sum_{i=0}^n y_i \ell_i(x)$.
• $\ell_i(x) = \Pi_{j \neq i} \frac{x - x_j}{x_i - x_j}$.
• $\ell_i(x_i) = 1$.
• $\ell_i(x_j) = 0$ for $j \neq i$.

Proof of Uniqueness

• Assume another polynomial $q(x)$ of degree at most $n$ exists such that $q(x_i) = y_i$ for all $i$.
• $r(x) = p(x) - q(x)$
• $r(x_i) = p(x_i) - q(x_i) = y_i - y_i = 0$
• $r(x)$ has $n+1$ roots.
• $r(x)$ is a polynomial of degree at most $n$.
• $r(x) = 0$.

Fast Fourier Transform (FFT)

• The goal is to evaluate a polynomial $p(x)$ of degree $n$ at $n+1$ points $x_0, \dots, x_n$ in $O(n \log n)$ time.
• Choose $x_0, \dots, x_n$ to be the $n+1$ roots of unity $\omega_k = e^{2\pi i k / (n+1)}$ for $k = 0, \dots, n$.

Divide and Conquer Approach

• $p(x) = \sum_{i=0}^n a_i x^i$
• $p(x) = p_{even}(x^2) + xp_{odd}(x^2)$, where $p_{even}(x) = \sum_{i=0}^{n/2} a_{2i} x^i$ and $p_{odd}(x) = \sum_{i=0}^{n/2} a_{2i+1} x^i$.
• $p_{even}(x)$ and $p_{odd}(x)$ are evaluated at the $(n+1)/2$ roots of unity.
• $\omega_k^2 = e^{2\pi i k / ((n+1)/2)}$ for $k = 0, \dots, (n+1)/2$
• Complexity is $T(n) = 2T(n/2) + O(n) = O(n \log n)$