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.

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.

In addition to handling very high degree polynomials, it is accurate, fast, uses minimum memory, and is programmed in the widely available language, Matlab.

The first evaluates the polynomial over a grid on the complex plane and conducts a direct search for potential 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.

In the first phase of this stage, a grid is designed with concentric circles of a particular radius intersected by a set of radial lines.

The positions and spacing of the radial lines and the circles are chosen to give a grid that will hopefully separate the expected roots.

Because the zeros of a polynomial with random coefficients have a fairly uniform angular distribution and are clustered close to the unit circle, it is possible to design an evaluation grid that fits the expected root density very well.

In the second phase of this stage, the polynomial is evaluated at the nodes of the grid using the fast Fourier transform (FFT).

The first phase consists of applying an iterative algorithm to improve the accuracy of the location found by the grid search.

This stage consumes the largest part of the execution time of the total factorization, but it is crucial to the final accuracy of the roots.

If, in the unusual case, these further iterations of deflation do not find all of the missing zeros, a new, finer grid is constructed and the whole process started again at stage one.

But, if they happen or if factoring an ill-conditioned polynomial is attempted, the roots will be found with the Lindsey–Fox program in most cases but with reduced accuracy.

Because the FFT is such an efficient means of evaluating the polynomial, a very fine grid can be used which will separate all or almost all of the zeros in a reasonable time.

And because the searching and polishing is done on the original polynomial, they can be done on each root simultaneously on a parallel architecture computer.

For random coefficient polynomials, the number of zeros missed by the grid search and polish stages ranges from 0 to 10 or occasionally more.