Abstract

Let $a$ and $b$ be two polynomials having numerical coefficients. We consider the question: when are $a$ and $b$ relatively prime? Since the coefficients of $a$ and $b$ are approximant the question is the same as: when are two polynomials relatively prime, even after small pertubations of the coefficients?

In this paper we provide a fast algorithm for determining that two polynomials are prime, even under small pertubations of the coefficients. Our methods rely on an inversion formula for Sylvester matrices to establish an effective criterion for relative primeness. The inversion formula also allows for an estimate of the condition number of the linear problem. A modification of the well known Cabay-Meleshko numerical algorithm for Padé approximation is then used to compute the criterion for a given problem in a fast, numerically stable way.