A divide and conquer method for polynomial zeros

摘要

The problem of factorising an nth-degree polynomial Pn(x) = xn + a1xn−1 + ⋯ + an−1x + an, where the coefficients ai are real, into two polynomials Q(x) and R(x) of degrees nQ and nR can be posed as a system of n quadratic equations. An efficient implementation of Newton's method for the solution of these equations is achieved by exploiting the block Toeplitz structure of the Jacobian matrix which arises when nQ and nR are restricted to {m − 1, m, m + 1∣m = [12n]}, where [x] is the largest integer ⩽x. This polynomial factorisation permits the development of a divide and conquer method for the simultaneous calculation of all the zeros of a polynomial.