version 1.8.0.0 (600 Bytes) by
Feng Cheng Chang

Find polynomial GCD by "Leading-coefficient Elinimation"

In the longhand polynomial division given as

P(k) = P(k-2) - P(k-1)*Q(k)

The quotient Q(k) and the remainder P(k) are obtained from dividing the dividend P(k-2) by the divisor P(k-1). If we can make Q(k) = 1, by converting P(k-2) and P(k-1) into equal degree and monic, then the longhand polynomial division becomes simply the "monic polynomial subtraction" (MPS):

P(k) = P(k-2) - P(k-1)

For a pair of given polynomials p(x) and q(x) of degree n and m, n>m, we set

P(1) = p(x)/p_0

P(2) = q(x)*x^(n-m)/q_0

Applying the MPS repeatedly starting from k=3, until k=K+1, such that

P(K+1) = P(k-1) - P(k) = 0

then we get our desired polynomial GCD as

gcd(p,q) = P(K).

The source code uses only basic MATLAB built-in functions. Its listing is only 17 lines total !

Amazingly, this simple routine gives the expected results for the test polynomials and their derivatives of very high degree, such as

p(x) = (x + 1)^1000

p(x) = (x + 123456789)^30

p(x) = (1234x + 56789)^60

p(x) = (x^4-2x^3+3x^2-4x +5)^50

p(x) = (x^4 - 1)^25

*************** UPDATE (10/05/09): **************

The approach "Leading-coefficient Elinimation" is revised from the original "Monic Polynomial Subtraction".

It also reduces almost half of the total arithematic operations.

The total source code listing is only 12 lines!

*************** UPDATE (01/22/2018): **************

The source code function g = poly_gcd(p,q) is revised and updated. It greatly reduces the overall operation procedures.

Please see the typical examples in the comment section.

Feng Cheng Chang (2021). poly_gcd(p,q) (https://www.mathworks.com/matlabcentral/fileexchange/20859-poly_gcd-p-q), MATLAB Central File Exchange. Retrieved .

Created with
R13

Compatible with any release

- MATLAB > Mathematics > Elementary Math > Polynomials >

**Inspired:**
Polynomials with multiple roots solved

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

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Feng Cheng ChangTypical Examples:

Ex. 1,

p = poly([1 1 1 1 -2 -2 -2 -3 -3 4]); q = polyder(p),

p =

1 4 -17 -86 19 376 25 -734 100 600 -288

q =

10 36 -136 -602 114 1880 100 -2202 200 600

g = poly_gcd(p,q)

g =

1 4 -2 -16 5 20 -12

Ex. 2,

p = [225075 0 0 0 0 -20295], q = [88555 0 0 0 -12920],

p =

225075 0 0 0 0 -20295

q =

88555 0 0 0 -12920

g = poly_gcd(p,q)

g =

1 -0.61803

*** Refer to "Polynomial GCDs by Linear Algebra", Notes by Barry Dayton, March 2004. ***

Feng Cheng ChangPozos:

To answer your question, first find r the GCD of two given polynomials p and q, then, u=p/r, v=q/r and w=u*v.

The partial fraction expansion (PFE) of 1/w will give 1/w=y/u+x/v,

where the two desired polynomials x and y can thus be determined after performing reverse PFE. Thus,

1 = x*u+y*v, or

r=x*p+y*q.

In addition, we may also find the two polynomials t and s, so that

1=u/t+v/s, or

r=p/t+q/s.

It is interesting to note that x and y are expected to be, respectively, equal to 1/t and 1/s. However, it isn't so !

Please let me know if you want find out more detail derivation about these relations.

FC Chang

bullpoz PozosFC Chang:

I would like a favor.I've made a gui that represents the gcd

it is like this: r=poly_gcd(p,q)

i've been asked to make this:

r=xp+ψq

if you understand can you tell me how to show this expression out of the gcd code

Thanks

Feng Cheng ChangPozos:

I do not understand your question. But if you means that you want make a gui from my article, you may go ahead to do so.

Please see my other articles, such as "Solve multiple-root polynomials' that may refer computation of polynomial GCD.

FC Chang

bullpoz PozosWho can i make a gui of that?please help!