0.4 More details on the third stage of the lf algorithm

Addendum: more details of the third (unfactor and deflation) stage

The deflation stage of the Lindsey-Fox program first separates the unique, polished candidate roots that were found by the grid search and polish stages into two sets, one, a set very, very near the unit circle and the other, a set containing the rest of them. Both groups are unfactored in the frequency domain by the rootSpectrum program. It takes each zero or root, $r$ , forms the associated first degree factor, $(z-r)$ , and pads with zeros to a length which is a an appropriate power of 2; i.e. [1,-r,0,0,0,...]. The DFT's of these terms are computed and multiplied together to get the DFT of the coefficients of the candidate polynomial. Exception: if the degree is less than 500, Matlab's command “poly” is used to combine them. This is the second most time consuming part of the total program. The coefficients are calculated from the candidate zeros with the “ifft” command and compared to the original coefficients. If they are the same number, then the search and polish possibly found them all. If the polishing process says the roots are close and a comparison in the unfactoring process says the coefficients are close, then these are the two criteria for success.

If the grid search and polish stages did not find all of the zeros, the original polynomial is deflated by removing those zeros found from it. That is done by dividing the DFT of the coefficients of the original polynomial, point-by-point, by the DFT associated with the zeros away from the unit circle which are found by the rootSpectrum program (deflation in the frequency domain). This quotient polynomial is further deflated (this time in the coefficient domain) by deconvolving it with the inverse FFT of the DFT associated with the zeros very near the unit circle. The resulting new quotient polynomial is now the original polynomial with all of the zeros found by the grid search and polish stages removed from it. This, hopefully low degree, polynomial is factored with the Matlab “roots” function and polished, first against the quotient polynomial, then the original polynomial. These new candidate zeros are added to the set found by grid search and polish, their associated spectra multiplied by that found in the “unfactoring” function, then checked to see if there are enough and if their associated coefficients are close to the original coefficients. If the answer is yes to both, the factoring is finished. If there are too few zeros, deflation will be performed again. This is repeated until all of the zeros are found or until no new ones are found. If there are still too few, a new search grid is designed with a smaller cell size and started again in stage one.

The basic mathematics behind this program can be found here.