Polynomials with multiple roots solved

Find roots of a polynomial with very high degree and multiplicity by this compact routine.

Description

A given polynomial with multiple roots is solved by the routine
                  Z = polyroots(p), where
          Input: p polynomial coefficient vector, real or complex.
          Output: Z root-multiplicity pairs.

The MATLAB source code is very compact, using only basic MATLAB built-in functions, and existing double precision.

A short routine p = polyget(A) is also provided for creating a test polynomial coefficient vector.

This simple routine gives amazingly the expected results for test polynomials of very high degree and multiplicity, such as

          p(x) = (x -123456789)^9876
          p(x) = (x^8-1)^1000
          p(x) = (x^100-1)^100
          p(x) = (x^6 -1) *(x^5 -1)^2*(x^4 -1)^3*(x^3 -1)^4*(x^2 -1)^5*(x -1)^6
          p(x) = (x-1+2i)^9 *(z+3-4i)^8 *(z-5-6i)^7

For detail description, please refer to
F.C. Chang, "Solving multple-root polynomials" IEEE Antennas and Propagation Magazine, Vol.51, No.6, pp. 151-155, Dec. 2009.

Or get a pdf file by e-mail from [e-mail].

• MATLAB release: MATLAB 6.5 (R13)
• Other Files: license.txt, ; polyget.m, ; polyroots.m, ; polyroots_examples.doc, ; polyroots_examples.m

[Feng Cheng Chang]

Self comment:

Amazingly, the revised routine can find the desired roots of test polynomials p(x) -- expanded, such as
       p(x) = (x+987654321)^N,
where N=any positive integers, such as 10, 100, 1000, 10000, ....

For example, find the roots of the following polynomial expanded
       p(x) = (x+987654321)^12345.

>> format long g
>> p = poly([-987654321*ones(1,12345)]);
>> Z = poly_roots(p)
 Z =
          -987654321 12345

It takes about 2 min total time. Most is to create polynomial coefficient vector p, and only 0.5 sec to get the desired root-multiplicity pairs Z.

Of course, any numerical algorithm is not fool prove, neither is mine.

Foe example,it does work for p(x)=(9876x+12345)^70, but fails for p(x)=(9876x+12345)^80.

I hope someone would like to try it for some other existing test polynomials, and give me any valuable comments.