An algorithm for computing certified approximate GCD of \(n\) univariate polynomials (Q1295792)

The paper presents two algorithms for the problem of finding approximate gcd of \(n\) univariate polynomials. More precisely: Given a tolerance \(\varepsilon\) and polynomials \(P1,\ldots ,P_n\) of degree \(d_i\), respectively, find perturbations \(\delta P_i\) and a divisor \(D\) of \(P_i+\delta P_i\) satisfying: (i) \(\deg \delta P_i \leq d_i\), (ii) \(||\delta P_1,\ldots ,\delta P_n||< \varepsilon\), (iii) \(D\) has maximum degree. The author uses generalized Sylvester matrices together with Singular Value Decomposition (allowing a numerical approach) to device both algorithms. Bounds for the degree of the approximate gcd are obtained. Moreover, the first algorithm provides a certification of the degree. New algorithms for the problem with two polynomials are suggested. Finally, numerical examples with timings are presented, illustrating his computer implementation.