The Lindsey–Fox algorithm, named after Pat Lindsey and Jim Fox, is a numerical algorithm for finding the roots or zeros of a high-degree polynomial with real coefficients over the complex field. It is particularly designed for random coefficients but also works well on polynomials with coefficients from samples of speech, seismic signals, and other measured phenomena. A Matlab implementation of this has factored polynomials of degree over a million on a desktop computer.
The Lindsey–Fox algorithm 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 and reprinted in 1996. After further development, other papers were published in 2003 and an on-line booklet. The program was made available to the public in March 2004 on the Rice University web site. A more robust version-2 was released in March 2006 and updated later in the year.
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 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.
Stage one: the grid search for prospective zeros Construct a polar coordinate grid on the complex plane with spacing derived from the degree of the polynomial being factored Use the FFT to evaluate the polynomial at each node along the concentric circles of the grid. Search over each 3 × 3 set of values for relative minima. If the center value is less than the edge values, it is a prospective zero by the Minimum Modulus Theorem of complex analysis.
Stage two: polish the prospective zeros Apply Laguerre's algorithm to each prospective zero, correcting it to a better approximation of the “true” zero of the polynomial Test the set of polished zeros for uniqueness and discard any duplicates to give a set of candidate zeros
Stage three: unfactor, perhaps deflate, and verify Unfactor the polished zeros i.e., reconstruct a candidate polynomial in coefficient form from the polished candidate zeros If the degree of the reconstructed polynomial is the same as that of the original polynomial and differences in their coefficients are small, the factoring is successful and finished If some zeros were missed, deflate and factor the quotient polynomial. If that does not find all of the missed zeros, deflate and factor again until all are found or until no new ones are found If deflation finds all the zeros that it can, and it still has not found them all, design a new grid with a finer spacing and return to stage one. If four restarts do not find them all and/or the reconstruction error is not small, declare failure.
Description of the three stages
… excerpt ends here. Continue reading the full article.
