File Exchange

image thumbnail

Factoring a multiple-root polynomial

version (3.17 KB) by Feng Cheng Chang
A multiple-root polynomial is factored into lower-degree distict-root polynomials, then solved.


Updated 21 Apr 2008

View License

A given multiple-root polynomial is factored into lower-degree distict-root polynomials with natual-order-integer powers. All roots may thus be solved with easy.

The more multiplicities the polynomial roots possess, the more efficient the routine will be. This is contrary to the general public issue.

When coefficients of given polynomial are all integers, then this routine involves only simple arithmetric operations, such as pure integer addition and multiplication, and no floating point compuations in process. The round-off errors may thus be eliminated, if no numerical digital overflow occurs.

The crucial concern is polynomial GCD computation. The classical Euclidean GCD algorithm is employed here, even though it is numerically unstable.

Amazingly, this simple routine gives the exact results for test polynomials of fairly high degrees, such as

p(x) = (x + 1)^50
p(x) = (x^4 - 1)^25
p(x) = (x - 123456789)^4
p(x) = (123x + 456)^4
p(x) = (x^4 -2x^3 +3x^2 -4x +5)^12

F C Chang, "Factorization of Multiple-Root Polynomials,"

Cite As

Feng Cheng Chang (2021). Factoring a multiple-root polynomial (, MATLAB Central File Exchange. Retrieved .

Comments and Ratings (2)

Feng Cheng Chang

Short description of algorithm:

G(1) = p (given polynomial)
G(m) = Polygcd(G(m-1),polyder(G(m-1))),
m = 2, 3, … , M
G(M+1) = G(M+2) = … = 1.
U(m) = Polydiv(G(m),G(m+1)),
m = 1, 2, … , M+1
W(m) = Polydiv(U(m),U(m+1)),
m = 1, 2, … , M
p = Prod ( W(m)^m ) | m = 1, M

Self Comments:

This code has some restrictions and is not intended for general use.

All the coefficients of the original polynomial must be restricted to be real integer numbers.

All computations involve only elementary integer arithmetic operations, such as integer additions, integer subtractions, and integer multiplications. Only integer divisions are employed whenever an integer dividend is divisible by an integer divisor to obtain the integer quotient with no reminder, such as 6/3, 7/1, 7/7, … , but not 1/3, 6/4, … .

No floating-point computations involve in process, so the round-off errors may be eliminated. The computed results should be exact theoretically. However, the numerical digital overflow may occur since the integers involved are expected to be very huge numbers.

If a polynomial does not possess any multiple roots, then this code will at least reveal that all roots are distinct.

For the general root-finding routines without restrictions, the MATLAB software package of MULTROOT introduced by Zeng is highly recommended. Its routine Z = multroot(p) however requires algorithm of some advanced mathematics, such as the singular value decomposition and the least square iteration process. Nevertheless, it is cable to accurately calculate the roots with multiplicities of the high degree polynomial, using only the standard machine precision.

John D'Errico

The author has gone to great pains to write this code, and even written great reams of comments inside it. The code appears to work (I think.) So why have I not given this a better numeric rating?

The help is poor. In order to read the help, you cannot use the help facility in matlab, you need to edit the code. Editing the code is a poor thing to do, since you may accidently make a change to it, causing it to fail in the future. I'm sorry, but this is just ridiculous. Why not enable the existing help utility? When you type

help PolyFct

Matlab returns the contiguous block of comments at the top of the function to the command line. Unfortunately, the more useful part of the help in this tool has a blank (non-commented) line separating itself from the first contiguous comment block. So only the first part of the help appears.

Next, there is no H1 line. So this code fails to enable the lookfor utility in Matlab. How else will you remember the name of this code, "PolyFct.m" in a years time from now when you need it? Lookfor assumes that the FIRST comment line is a descriptive line with useful keywords in it. In the case of PolyFct, the fist comment line is blank. Its a poor use of whitespace here.

How else has the author done a disservice to his potential users? Even if you do edit the code to read the help, what is provided is of little use. The help for a function should tell you what the arguments mean. Is the input polynomial expected to be in matlab poly form? Or should it be symbolic?

The output arguments are never described. What do W, G, U mean? What forms do they take?

There is no error checking in the code. What if the user inputs a symbolic polynomial? Good code might convert it into a numerical set of coefficients, as are required here. Or at least it would be friendly and remind the user what the inputs should be.

I did find examples of use in the comments, although they don't appear in when you use help.

I'd like to test the code more fully, but if I'm not really positive what it should return, how can I test it?

Overall, a 3 rating seems to be a fair choice for this tool. I'd have happily given it a higher rating were I given an excuse. Perhaps the author will choose to improve this tool so that I have an excuse to raise my rating.

MATLAB Release Compatibility
Created with R13
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!