An algorithm for computing certified approximate GCD of \(n\) univariate polynomials (Q1295792)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An algorithm for computing certified approximate GCD of \(n\) univariate polynomials |
scientific article |
Statements
An algorithm for computing certified approximate GCD of \(n\) univariate polynomials (English)
0 references
26 June 2000
0 references
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.
0 references
Approximate GCD
0 references
Sylvester matrices
0 references
Singular Value Decomposition
0 references