2
$\begingroup$

Suppose I have given a rational function $r(x)=p(x)/q(x)$ where $p$ is a degree $m$ polynomial and $q$ is a degree $n$ polynomial, both over the real numbers, and the coefficients of $p$ and $q$ are represented by floating point numbers, which are the result of some computational procedure (I am working on recursive filtering of measurement data, if that is of interest to somebody).

If $p$ and $q$ share some common linear factor (e.g. $x-1$), the corresponding root (in the example it's $x_0=1$) represents a removable singularity of $r$.

But due to the finite precision of numerical processing, $p$ might have a root $x^\prime_0=1.0001$, whereas $q$ might have a root $x^{\prime\prime}_0=0.9999$, and the only reason why these roots differ is due to rounding error while generating the coefficients. I would like to be able to remove such singularities, although they are not removable in the true sense of the word with the roots being different.

So what I am trying to do is perform an approximate greatest common divisor algorithm $$\text{gcd}_{\text{approx}}(p,q,\delta)$$ that eliminates common roots with a precision limit $\delta$. Two roots are considered different if their difference is above the precision limit, for example:

$$\text{gcd}_{\text{approx}}(x-1.01, x-0.99, 0.001) = 1$$

whereas the roots are considered identical if their difference is less than the precision limit, for example:

$$\text{gcd}_{\text{approx}}(x-1.0001, x-0.9999, 0.001) = x-1$$

I have tried to develop this out of the well known Euclidean gcd algorithm, but I can't seem to be able to make sense out of the final residual that is obtained when roots differ slightly.

I can't believe that this is an open problem...

$\endgroup$
  • $\begingroup$ One idea that I have seen discussed in several places is to take the Sylvester matrix, do an SVD on it and with that do a rank estimation. The rank or rank deficit is connected to the degree of the approximate common factor. Somehow from the orthogonal factors you can read off either the common factor or the reduced polynomials. $\endgroup$ – LutzL Nov 30 '18 at 15:00
  • $\begingroup$ I guess I see the idea. But isn't SVD about as costly as complete root-finding for my polynomials? So if I can afford computing all roots, I can just determine the distance between all pairs of roots directly and just sort those out, that are close together, right? $\endgroup$ – oliver Nov 30 '18 at 15:12
  • 1
    $\begingroup$ The problem of finding root clusters is closely related, as a root cluster is almost a multiple root. There you want to find and remove approximately common factors of polynomial and its derivative. There might be more literature published lately on that topic than on the approximate gcd problem. Kaltofen did some papers on approximate polynomial algorithms. $\endgroup$ – LutzL Nov 30 '18 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.