Purpose

This file contains two functions, lroots() and broots(), described in "Factoring Very High Degree Polynomials" in the November 2003 issue of "Signal Processing Magazine." These programs are designed to factor the z-transforms of speech data, seismic data, and real random coefficient polynomials. These polynomials all have very similar root distributions. Furthermore, it is suspected that many polynomials whose coefficient sequences are not asymptotic to zero at either end will have similarly distributed roots. Therefore, although these programs may not work well for the general polynomial, they are likely to work for a large and important subclass of polynomials - especially those arising from physical signals.

Broots() succeeded in factoring a few polynomials of degree 100,000, but always failed at degree 150,000. Lroots() has been tried on and succesfully factored two polynomials of degree 2,080,000 and two of degree 2,000,000. The larger polynomials took 5.9 days on a 3 GHz Dell computer running Windows. The algorithm of lroots() is O(N²) so it is estimated that a degree 4 million would take 24 CPU days. A 4 million degree polynomial has been factored on four processors of a AMD cluster in 5.3 days using a parallel version of the program.

This file also contains 3 functions for phase unwrapping - unwrapz, unwrapph, and unwrapm.

Why is this code significant? Matlab's polynomial factorization function, roots(), uses the eigenvalue method. This is an extremely powerful method for low and medium degree polynomials. However, it has problems with high degree because it is O(n^3) in operation count and it is O(n^2) in workspace. By contrast, lroots() is O(n^2) in operation count and O(n) in workspace. On a 2.66 GHz computer with 1 GB memory, roots() took 3.7 hours to factor a 5,000 degree polynomial; lroots() got the same answer in 6 seconds. On this computer, any attempt to use roots() to factor a 6,000 degree polynomial immediately returned the error message, "Out of memory" because Matlab could not allocate the 6,001x6001X(8 bytes)=288 MB work array. On this computer, lroots() does not start to get "Out of memory" problems until it gets to degree 2^19-1=524,287, and even then there is a slow work-around by artificially making the radial grid spacing smaller

These programs are also important because phase unwrapping can be done accurately if it is possible to accurately factor the corresponding z-transform. Phase unrapping is a step in the cepstral transform.