Computing Approximate GCDs in Ill-conditioned Cases
Masaru Sanuki, Tateaki Sasaki · 2007
The ill-conditioned cases we consider are 1) the small leading-coefficient case, 2) small leading-coefficient GCD case, 3) big leading coefficient case, and 4) approximately singular leading-coefficient case. We propose three new algorithms for computing the approximate GCDs in these cases. The first one is to stabilize the univariate PRS by avoiding the division by polynomials of small leading coefficients. The second and the third ones are modifications of the QRGCD and the (approximate) PC-PRS methods, respectively, for multivariate polynomials. Furthermore, we propose a device to remove fully-erroneous terms arising from the exact cancellation. Some experiments show that our algorithms remove the instability considerably and work quite efficiently.