A NEW AND EFFICIENT PROGRAM FOR FINDING ALL POLYNOMIAL ROOTS


			       M. Lang
     Department of Electrical and Computer Engineering - MS366
              Rice University, Houston, TX-77251

			    B.-C. Frenzel
	    Institut fuer Elektrische Maschinen, TU Berlin
	       Einsteinufer 11, D-10587 Berlin, Germany



			       ABSTRACT

Finding polynomial roots rapidly and accurately is an important
problem in many areas of signal processing. We present a new program
which is a combination of Muller's and Newton's method.  We use the
former for computing a root of the deflated polynomial which is a good
estimate for the root of the original polynomial.  This estimate is
improved by applying Newton's method to the original polynomial. Test
polynomials up to the degree 10000 show the superiority of our program
over the best methods to our knowledge regarding speed and accuracy,
i.e., Jenkins/Traub program and the eigenvalue method. Furthermore we
give a simple approach to improve the accuracy for spectral
factorization in the case there are double roots on the unit
circle. Finally we briefly consider the inverse problem of root
finding, i.e., computing the polynomial coefficients from the roots
which may lead to surprisingly large numerical errors.