numerical algorithms for determining least common multiple of polynomials

Question

I have a pair of rational polynomial fractions $\frac{A(x)}{B(x)} + \frac{C(x)}{D(x)}$ where A, B, C, and D are all polynomials in x, and I have their coefficients as an array of numbers.

I would like to reduce them to a common denominator numerically without running into numerical errors, so I don't want to write it as $\frac{A(x)D(x)+B(x)C(x)}{B(x)D(x)}$.

Here's my question: is there a good numerical algorithm for determining polynomial factors $K_B(x)$ and $K_D(x)$ along with the least common multiple of $B(x)$ and $D(x)$, such that $LCM(B(x),D(x)) = K_B(x)B(x) = K_D(x)D(x)$ ?

Because then I can write the sum as $\frac{A(x)K_B(x)+C(x)K_D(x)}{LCM(B(x), D(x))}$.

My gut feeling is that if I try to do this by finding the roots of $B(x)$ and $D(x)$ numerically, I may be doing a lot more work than I need.

Answer 1

never mind, I think I got it; I just use the Euclidean algorithm. (Ick. This has numerical issues.)

In Python, for example:

import numpy as np

def polygcd(a,b):
    '''return monic GCD of polynomials a and b'''
    pa = a
    pb = b
    M = lambda x: x/x[0]
    # find gcd of a and b
    while len(pb) > 1 or pb[0] != 0:
        q,r = np.polydiv(pa,M(pb))
        pa = pb
        pb = r
    return M(pa)

def polylcm(a,b):
    '''return (Ka,Kb,c) such that c = LCM(a,b) = Ka*a = Kb*b'''        
    gcd = polygcd(a,b)
    Ka,_ = np.polydiv(b,gcd)
    Kb,_ = np.polydiv(a,gcd)
    return (Ka,Kb,np.polymul(Ka,a))

---

edit: Hmm -- I still need to have some kind of numerical tolerance; comparing with zero isn't going to guarantee proper behavior in the face of floating-point representation errors.

This problem is an "interesting" one (e.g. not that easy to solve), apparently:

• http://math.univ-lille1.fr/~bbecker/ano/pub/1997/ano369.pdf
• http://www.mathcs.emory.edu/~boito/newfifthspecial.pdf
• http://www.mathcs.emory.edu/~boito/thesis.pdf