# numerical algorithms for determining least common multiple of polynomials

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.

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: