Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31100
Factoring a Polynomial with Multiple-Roots

Authors: Feng Cheng Chang


A given polynomial, possibly with multiple roots, is factored into several lower-degree distinct-root polynomials with natural-order-integer powers. All the roots, including multiplicities, of the original polynomial may be obtained by solving these lowerdegree distinct-root polynomials, instead of the original high-degree multiple-root polynomial directly. The approach requires polynomial Greatest Common Divisor (GCD) computation. The very simple and effective process, “Monic polynomial subtractions" converted trickily from “Longhand polynomial divisions" of Euclidean algorithm is employed. It requires only simple elementary arithmetic operations without any advanced mathematics. Amazingly, the derived routine gives the expected results for the test polynomials of very high degree, such as p( x) =(x+1)1000.

Keywords: Polynomial roots, greatest common divisor, Longhand polynomial division, Euclidean GCD Algorithm

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1258


[1] Z. Zeng, "Computing multiple roots of inexact polynomials," Math. Comput, 74 (2005), pp. 869-903.
[2] F.C. Chang, "GCD of two univaiate polynomials by monic polynomial subtractions," submitted to Appl. Math. Comput.
[3] W.S. Brown and J.F. Traub, "On Euclid-s algorithm and the theory of subresultants," J. ACM 14 (1) (1967), pp. 128-142.
[4] I.S. Pace and S. Barnett, "Comparison of algorithm for calculation of GCD of polynomials," Int. J. System Scien, 4 (1973), pp. 211-226.
[5] M. Mitrouli and N. Karcanias, "Comutation of the GCD of polynomials using Gaussian transformation and shifting," Int. J. Control, 58 (1993), pp. 211-228.
[6] A. Terui, "Recursive polynomial remainder sequence and its subresultants," J. Algebra, (2008).
[7] C.D. Yan and W.H.Chieng, "Method for finding multiple roots of polynomials," Int. J. Computers & Mathematics with Applications, 51 (2006), pp. 605-620.