FFT-based fast polynomial rooting
L. Hoteit · 2002
A fast, accurate and robust approach is proposed for the computation of the roots of complex polynomials. The method is derived from the DFT-based differential cepstrum estimation for moving average signals. This minimum/maximum-phase polynomial factorisation is easily extended to a factorisation along an arbitrary circle. In an iterative fashion, we estimate the largest root modulus from the differential cepstrum, then factor out the associated root(s) from the polynomial. For band-limited signals with roots located along the unit circle, the polynomial origin is slightly perturbed prior to the application of the algorithm. On average, three fast Fourier transforms are required per polynomial root, offering a significant computational advantage in the root estimation of moderate to high order polynomials.