A divide and conquer method for polynomial zeros (Q911228)

It is shown that the factorization of a polynomial with real coefficients into two polynomials permits the development of a divide and conquer method for numerical calculation of all the zeros of the polynomial. The proposed algorithm is based on a Newton iteration to solve the quadratic equations which relate the unknown coefficients of those two factors to the known coefficients of the given polynomial. In a Newton iteration, a system of linear equations with the Jacobian matrix of quadratic equations as the coefficient matrix is solved. By exploiting the block Toeplitz structure of the Jacobian matrix, the Newton iteration can be implemented very efficiently. Numerical performance of the proposed method is given to illustrate its computational efficiency.