Information in the Spectrum of the Polynomial Coefficients
Summary: Describes how the Spectrum (or Fourier Transform) of polynomial coefficients gives information about the conditioning of the roots of the polynomial near the unit circle. The author of this module is Jim Fox.
Insights From the Amplitude Spectrum
The Spectral Significance of Deflating One Root
A root, r, corresponds to a linear factor z-r and to the time series [1, -r]. If this is padded with zeros and the FFT computed, its amplitude spectrum is basically v-shaped with curved sides and a minimum whose index/frequency is computable from the root’s argument. The transform is the linear function taking 0 radians to 0 Hertz and pi radians to Nyquist frequency. If the complex FFT generates an amplitude spectrum with N points, the linear factor corresponding to a root with argument 2*pi/c has a minimum at index 1+N/c. It is a notch filter; the closer the root is to the unit circle, the deeper the notch. Thus, when a root is deflated, it removes a notch and the spectrum of the quotient will therefore tend to have a local peak at the corresponding index. Therefore, deflating a root pushes up the spectrum at a frequency/index that can be computed from its argument.
The first figure below shows the real FFT amplitude spectrum of a 127-degree mean-0 real random coefficient polynomial. It is called a flat spectrum or a white noise spectrum. The next figure shows the real amplitude spectrum after a root and its complex conjugate have been deflated. The root was the one with argument closest to 2*pi/4. The root's magnitude was .994, i.e. near 1.0, so the minimum of its spectrum is close to 0 and deflating it dramatically increased the spectrum at index 1+128/4=33. If the root had not been so close to zero, the increase near sample 33 would have been less pronounced.
 |
 |
The observation that deflating a root increases the spectrum at a predictable frequency leads to the FFT Argument Selection method.
The Correlation of the Amplitude Spectrum With Root Error Estimates
The next figure shows the 200-degree polynomial that is supplied with this package. Half the roots are ill-conditioned and a few are extremely ill-conditioned. Of the 201 samples, it alternates sign at 178 samples. The dynamic range is 1 to 1.4x107
 |
By default, the root polishers supplied in this package apply corrections to an estimated root position until either the correction is extremely small or until a relatively large number corrections have been applied. The polishers can optionally return an error estimate for each root. The next figure shows a surprising correlation between the logarithm of the root error estimates and the logarithm of the amplitude spectrum of the previous polynomial. The continuous curve is the real amplitude spectrum in dB scale normalized so that Nyquist frequency equals 180. Each + corresponds to an affine re-scaling of one error estimate, in dB scale, cross-plotted as a function of the root’s argument in degrees. The re-scaling caused the most ill-conditioned roots, the ones with the largest error estimates, to be the most negative.
 |
If a root had an argument that corresponded to a frequency where the amplitude spectrum was small, the error estimate was large; i.e., the root was ill-conditioned. The smaller the spectrum, the more severe the ill-conditioning. This figure is a surprisingly good correlation.
Additional Confirmation of This Correlation
- This correlation implies that a polynomial with a relatively flat amplitude spectrum, i.e. one with a small dynamic range, will have all its roots well conditioned. Random coefficient polynomials have flat amplitude spectra. When it has been examined, every root of random coefficient polynomials has always been extremely well conditioned - for degree less than 1,000 the error estimate are almost always less than 7x10-15. However higher degree have higher error estimates.
- The fact that random coefficient polynomials seem to always have well conditioned roots leads to two new factorization methods, FFT Argument Selection and Coefficient Pre-whitening, and the success of these methods is another confirmation.
- Multiple roots have been mathematically proven to be ill-conditioned. They will have a relatively small spectral value at the frequency corresponding to their argument because the contribution to the spectrum from the double root is the product of two identical notch filters.
- It has been observed that deflating several nearby roots of a random coefficient polynomial produces quotients with some ill-conditioned roots. Deflating one root pushes up the spectrum at the corresponding frequency. Deflating several nearby roots dramatically pushes up the spectrum for a small number of nearby frequencies leaving the spectrum small elsewhere. It is believed that this is the reason for the success of the Argument Randomization method with random coefficient polynomials.
If a polynomial has most roots near the unit circle but they are not uniformly distributed in argument, the spectrum will not be flat. Each root is a notch filter so if some range of arguments has an excessive number of roots, the spectrum will be lower at the corresponding frequencies. The more roots in a sector, the deeper the spectrum. The next figure shows the data from a histogram of the arguments of the roots of the previous polynomial linearly rescaled so that large histogram values became large negative values. The correlation is not as good as the previous plot but it seems to have some validity. Perhaps the correlation would have been better if the data had been weighted so that points farther from the unit circle were given less weight.
 |
Counterexamples to This Correlation
- The closer a root is to the unit circle, the deeper the spectral notch. If the spectrum is small near some frequency due to an isolated root very close to the unit circle, it need not be ill-conditioned. For example a mean 0 real random coefficient polynomial was created and factored. This forced 1.0 to be a root. The roots closest to i and -i were replaced by i and -i exactly. When the “roots” were unfactored, the resulting polynomial’s real spectrum was virtually 0 at 0 and Nyquist/2 frequencies. However, both 1.0 and i were extremely well conditioned roots. The correlation was not valid. Perhaps the reason is that the spectrum was small for only a very small band of frequencies.
- Wilkinson’s polynomial with roots -1, -2, -3, … -20 has spectrum 0 at Nyquist because -1 is a root and it is an n-th root of unity. However, -1 is well-conditioned as are the smallest magnitude roots. All roots have the same argument but it is only the larger magnitude roots that are ill-conditioned. The correlation was only partially valid.
For Further Research
- The above counterexamples need further explanation.
- Are there other counterexamples?
- No one has examined whether this correlation is true for non-polynomials. Perhaps, if the Laplace transform is small near a root of an arbitrary analytic function, the root can not be numerically determined accurately. If this is true, then something analogous to the Coefficient Pre-whitening method might improve the accuracy of root determination.
jwf 9/2/2006
Comments, questions, feedback, criticisms?
Send feedback
- E-mail the author of the module, Information in the Spectrum of the Polynomial Coefficients
Footer
More about this content: Metadata | Version History
This work is licensed by C. Sidney Burrus under a Creative Commons Attribution License (CC-BY 2.0).
Last edited by C. Sidney Burrus on Dec 5, 2007 9:30 pm US/Central.