The Lindsey-Fox Algorithm for Factoring Polynomials

The Lindsey-Fox algorithm uses the FFT (fast Fourier transform) to very efficiently conduct a grid search in the complex plane to find accurate approximations to the N roots (zeros) of an Nth degree polynomial. The power of this grid search allows a new polynomial factoring strategy that has proven to be very effective for a certain class of polynomials.

This algorithm is implemented in a package of computer programs created to factor high-degree polynomials. It was originally designed and has been further developed to be particularly suited to polynomials with real, random coefficients. In that form, it has proven to be very successful by factoring thousands of polynomials of degrees from one thousand to hundreds of thousand as well as several of degree one and two million. In addition to handling very high degree polynomials, it is accurate, fast, uses minimum memory, and is programmed in the widely available language, Matlab. There are practical applications, often cases where the coefficients are samples of some natural signal such as speech or seismic signals, where the algorithm is appropriate and useful. However, it is certainly possible to create special, ill-conditioned polynomials that it cannot factor, even low degree ones. The basic ideas of the algorithm were published in 1992 [1] and reprinted in 1996 [2]. After further development, another paper was published in 2003 [3]. The program was made available to the public in March 2004 on the Rice University web site [14]. A more robust version-2 will be released in March 2006.

• The 3 stages
• Details
• Timings
• References
• Addendum: Third Stage Details
• Addendum: Mathematical Principles