Future Changes

• 1) Use nroots(x,r) to design an intelligent search grid. Program lroots uses the polynomial degree to generate a search grid that should work if the polynomial is speech-like or random coefficient. If it is not random coefficient and the initial grid search fails, the program automatically generates a few additional search grids that are both finer and extend farther from the unit circle. The method of generation is very slow and crude because it depends only on the polynomial degree, not on the specific polynomial.

  This file contains a program, nroots(x,r), which can approximately find the number of roots of a polynomial x with magnitude < r. It does this by computing the winding number, not by factoring the polynomial. The returned answer should be close to correct but it can be in error if there are roots with magnitude very close to r. One should be able to call nroots several times with different values of r and use the results to intelligently design a search grid. This would be a huge improvement to lroots.

• 2) Improve the way error estimates are computed for every root. Accurate error estimates are un-important for speech-like random coefficient polynomials, but they are very important for polynomials with ill-conditioned roots.
• 3) Write a routine that uses nroots(x,r) to search for a few missing roots.

  For example, a previous version of lroots could not factor a certain polynomial called degree200. It failed to find 7 roots and their conjugates. The magnitudes of the missing roots were 0.9803, 0.9842, 0.9878, 0.9890, 0.9923, 0.9948, and 1.0084. These magnitudes could be approximately determined using nroots. Let z be the incomplete set of roots obtained using lroots.

  >> nroots(coeff, 1.01) % Hopefully the number of roots with magnitude < 1.01
  ans = 128

  >> length(find(abs(z)<1.01)) % The number of roots found with magnitude < 1.01
  ans = 114

  Thus, z is missing 14 roots (7 complex roots and their conjugates) with magnitude < 1.01. Furthermore,

  >> nroots(coeff, .97)
  ans = 32

  >> length(find(abs(z)<.97))
  ans = 32

  Thus all the missing roots have magnitude > .97. Finally,

  EDUğ nroots(coeff,.995)
  ans = 86

  EDUğ length(find(abs(z)<.995))
  ans = 74

  Thus z is missing 12 roots with magnitude < .995. (Six complex roots and their conjugates.)

  Thus, there are 6 complex conjuage pairs of missing roots with magnitudes between .97 and .995 and an additional missing pair with magnitude < 1.01.

  Furthermore, it is also often possible to use nroots to find the arguments of missing roots. Nroots uses the FFT to efficiently evaluate the polynomial at r*(the n'th roots of unity) where r is the radius of interest. Nroots optionally outputs the last set of polynomial evaluations, pval. The index where the absolute value of the polynomial evaluations achieves its minimum can point to the argument of a missing root. There is a natural correspondence between index and radians. [0, length(pval)] -> [0, pi] radians. To find the minimum and convert to radians,
  (find(pval==min(pval))-1)/(length(pval)-1)*pi

  For example, the largest missing root of degree200 satisifed:

  >> [abs(r), angle(r)]
  ans = 1.0084 2.3318

  Note,

  >> [n, pval] = nroots(coeff, 1.0087);
  >> [n, (find(pval==min(pval))-1)/(length(pval)-1)*pi]
  ans = 126.0000 2.3317

  >> [n, pval] = nroots(coeff, 1.0069);
  >> [n, (find(pval==min(pval))-1)/(length(pval)-1)*pi]
  ans = 124.0000 2.3317

  The "124" and "126" show that there is one root, and its complex conjugate, with radii between 1.0069 and 1.0087. As above, the actual magnitude is 1.0084. Furthermore, at both 1.0069 and 1.0087 the minimum absolute value of the polynomial evaluations is achieved at 2.3317 radians. As above, the actual argument of the root is 2.3318. Thus, in this case, nroots could be used to approximately find the magnitude and argument of this root.

  Unfortunately, there are at least 3 problems with using nroots(x,r). First it is slow. Second, nroots is unreliable if there several roots with magnitude near r. Nroots may return an answer that is slightly too large or too small. Third, suppose there is a missing root with magnitude 1.05 and argument 1.333. It is possible that nroots(x,1.01)==130 and nroots(x,1.08)==132 and in both cases the minimum of pval occurs at 2.432 radians, not 1.333. In other words we have the radius correctly bracketed but the argument is wrong. This has been observed to happen when there was an unusually large number of roots with magnitudes between 1.000 and 1.009 and arguments near 2.432. This large number of roots caused abs(f(z)) to be unusually small near 2.432 radians. Therefore when abs(pval) was examined along the circles with magnitude 1.01 and 1.08, the smallest values happened at 2.432. However, the second smallest relative minimum of abs(f(z)) did indeed occur at 1.333. Also, if you bracketed it more exactly, eg. nroots(x,1.04) and nroots(x,1.06), then the min of abs(pval) did indeed occur at 1.333 along both circles.