0.1 The lindsey-fox algorithm for factoring polynomials  (Page 3/3)

Stage two is more traditional than the other two. It “polishes” each of the prospective zeros found by the grid search. The first phase consists of applying an iterative algorithm to improve the accuracy of the location found by the grid search. In earlier versions of the program, Newton’s method was used but analysis and experiment showed that Laguerre’s method [18,19] was both more robust and more accurate. Even though it required more calculation than Newton’s method for each iteration, it converged in fewer iterations. The second phase of the second stage checks for duplications. A “fuzzy” uniqueness test is applied to each zero to eliminate any cases where on two or more prospective zeros, iterations converged to the same zero. If the number of unique, polished zeros is less than the degree of the polynomial, deflation later will be necessary. If the number is greater, some error has occurred. 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. One of the two criteria for success in factoring a polynomial is that each root must have been successfully polished against the original polynomial.

Stage three has several phases and possible iterations or even restarting. The first phase of the third stage takes all of the unique, polished zeros that were found in the first two stages and multiplies them together into the coefficient form of a candidate polynomial (“unfactors” the zeros). If the degree of this reconstructed polynomial is the same as that of the original polynomial and if the difference in their coefficients is small, the factorization is considered successful. Often, however, several zeros were missed by the grid search and polish processes of stage one and two, or the uniqueness test discarded a legitimate zero (perhaps it is multiple), so the original polynomial is “deflated” (divided) by the reconstructed polynomial and the resulting (low degree) quotient is factored for the missing zeros. If that doesn’t find them all, the deflation process is repeated until they are all found. This allows the finding of multiple roots (or very tightly clustered roots), even if some of them were discarded earlier. 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. More details on the third stage are in another module.

Multiple order and clustered roots are unusual in random coefficient polynomials. 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. If there are multiple order zeros (Mth order with M not too high), the grid search will find them, but with multiplicity one. The polishing will converge to the multiple order root but not as fast as to a distinct root. In the case of a cluster with Q zeros that fall within a single cell, they are erroneously identified as a single zero and the polishing will converge to only one of them. In some cases, two zeros can be close to each other in adjacent cells and polish to the same point. In all of these cases, after the uniqueness test and deflation, the quotient polynomial will contain a M-1 order zero and/or Q-1 zeros clustered together. Each of these zeros will be found after M-1 or Q-1 deflations. There can be problems here because Laguerre’s polishing algorithm is not as accurate and does not converge as fast for a multiple zero and it may even diverge when applied to tightly clustered zeros. Also, the condition of the quotient polynomial will be poorer when multiple and clustered zeros are involved. If multiple order zeros are extremely far from the unit circle, the special methods for handling multiple roots developed by Zhonggang Zeng [5] are used. Zeng’s method is powerful but slow, and hence only used in special cases [6]. References

Successful completion of the factoring of a polynomial requires matching zeros on the complex plane measured by the convergence of Laguerre’s algorithm on each of the zeros. It also requires matching the polynomial reconstructed from the found zeros with the original polynomial by measuring the maximum difference in each coefficient.

Characteristics of the lindsey-fox algorithm

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 of the fineness of the grid, the starting point is close to the actual zero and the polishing almost always converges in a small number of steps (convergence is often a serious problem in traditional approaches). 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. Because the searching is done on a 3 by 3 cell of the grid, no more that three concentric circles of the grid need be kept in memory at a time, i.e., it is not necessary to have the entire grid in memory. And, some parallelization of the FFT calculations can be done.

Deflation is often a major source of error or failure in a traditional iterative algorithm. Here, because of the good starting points and the powerful polisher, very few stages of deflation are generally needed and they produce a low order quotient polynomial that is generally well-conditioned. Moreover, to control error, the unfactoring (multiplying the found roots together) is done in the FFT domain (for degree larger than 500) and the deflation is done partly in the FFT domain and partly in the coefficient domain, depending on a combination of stability, error accumulation, and speed factors.

For random coefficient polynomials, the number of zeros missed by the grid search and polish stages ranges from 0 to 10 or occasionally more. In factoring one 2 million degree polynomial, the search and polish stages found all 2 million zeros in one grid search and required no deflation which shows the power of the grid search on this class of polynomial. When deflation is needed, one pass is almost always sufficient. However, if you have a multiple zero or two (or more) very, very closely spaced zeros, the uniqueness test will discard a legitimate zero but it will be found by later deflation. Stage three has enough tests and alternatives to handle almost all possible conditions. But, by the very definition of random coefficients, it is hard to absolutely guarantee success.

The timings of the The Lindsey-Fox program can be found here and examples of root distributions of polynomials with random coefficients are here.