0.1 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 was conceived of by Pat Lindsey and implemented by Jim Fox 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 million and one each of degree two million and four 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 first published by Lindsey and Fox 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 was released in March 2006 and updated later in the year. The references are in a separate module.

The three stages of the lindsey-fox program

The strategy implemented in the Lindsey-Fox algorithm to factor polynomials is organized in three stages. The first evaluates the polynomial over a grid on the complex plane and conducts a direct search for potential zeros. The second stage takes these potential zeros and “polishes” them by applying Laguerre’s method [18,19] to bring them close to the actual zeros of the polynomial. The third stage multiplies these zeros together or “unfactors” them to create a polynomial that is verified against the original. If some of the zeros were not found, the original polynomial is “deflated” by dividing it by the polynomial created from the found zeros. This quotient polynomial will generally be of low order and can be factored by conventional methods with the additional, new zeros added to the set of those first found. If there are still missing zeros, the deflation is carried out until all are found or the whole program needs to be restarted with a finer grid. This system has proven to be fast, accurate, and robust on the class of polynomials with real, random coefficients and other similar, well-conditioned polynomials.