An algorithm for computing certified approximate GCD of n univariate polynomials
From MaRDI portal
An algorithm for computing certified approximate GCD of \(n\) univariate polynomials
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.
Recommendations
- Toward the best algorithm for approximate GCD of univariate polynomials
- On approximate GCDs of univariate polynomials
- An iterative method for calculating approximate GCD of univariate polynomials
- Computation of approximate polynomial GCDs and an extension
- The approximate GCD of inexact polynomials
- GPGCD: an iterative method for calculating approximate GCD of univariate polynomials
- Approximate GCD of several univariate polynomials with small degree perturbations
- A heuristic verification of the degree of the approximate GCD of two univariate polynomials
- Computing approximate GCD of multivariate polynomials
- Certified approximate univariate GCDs
Cites work
- Certified approximate univariate GCDs
- Detection and validation of clusters of polynomial zeros
- scientific article; zbMATH DE number 4213315 (Why is no real title available?)
- scientific article; zbMATH DE number 42759 (Why is no real title available?)
- scientific article; zbMATH DE number 1254251 (Why is no real title available?)
- scientific article; zbMATH DE number 1254271 (Why is no real title available?)
- scientific article; zbMATH DE number 953021 (Why is no real title available?)
- Products of polynomials in many variables
- Quasi-gcd computations
Cited in
(52)- A computational study of ruled surfaces
- Approximate GCD and its application to ill-conditioned algebraic equations
- Certified approximate univariate GCDs
- A subspace method for the computation of the GCD of polynomials
- Structured matrix methods computing the greatest common divisor of polynomials
- Computation of approximate polynomial GCDs and an extension
- Toward the best algorithm for approximate GCD of univariate polynomials
- Approximate polynomial GCD by approximate syzygies
- Generalized algorithms for the approximate matrix polynomial GCD of reducing data uncertainties with application to MIMO system and control
- Nearest common root of a set of polynomials: a structured singular value approach
- Variable projection methods for approximate (greatest) common divisor computations
- Approximate gcds of polynomials and sparse SOS relaxations
- Computation of the topology of real algebraic space curves
- Approximate greatest common divisor of many polynomials, generalised resultants, and strength of approximation
- Matrix representation of the shifting operation and numerical properties of the ERES method for computing the greatest common divisor of sets of many polynomials
- Computing greatest common divisors and squarefree decompositions through matrix methods: the parametric and approximate cases
- A subresultant based subspace method for the computation of polynomial GCDs
- GCD of multivariate approximate polynomials using beautification with the subtractive algorithm
- Challenge to fast and stable computation of approximate univariate GCD, based on displacement structures
- Computing GCRDs of approximate differential polynomials
- An iterative method for calculating approximate GCD of univariate polynomials
- Numerical and symbolical methods for the GCD of several polynomials
- Computing multivariate approximate GCD based on Barnett's theorem
- A fast algorithm for approximate polynomial gcd based on structured matrix computations
- Approximate GCD a la dedieu
- Computing approximate GCD of multivariate polynomials
- Approximate Gröbner bases, overdetermined polynomial systems, and approximate GCDs
- Regularization and matrix computation in numerical polynomial algebra
- GPGCD: an iterative method for calculating approximate GCD of univariate polynomials
- Approximate GCD of several univariate polynomials with small degree perturbations
- scientific article; zbMATH DE number 1254251 (Why is no real title available?)
- scientific article; zbMATH DE number 1254271 (Why is no real title available?)
- scientific article; zbMATH DE number 1303542 (Why is no real title available?)
- The computation of multiple roots of a polynomial
- DISPLACEMENT STRUCTURE IN COMPUTING APPROXIMATE GCD OF UNIVARIATE POLYNOMIALS
- Computing multiple roots of inexact polynomials
- The approximate GCD of inexact polynomials
- A heuristic verification of the degree of the approximate GCD of two univariate polynomials
- scientific article; zbMATH DE number 953021 (Why is no real title available?)
- Overdetermined Weierstrass iteration and the nearest consistent system
- Certified Hermite Matrices from Approximate Roots - Univariate Case
- The GPGCD algorithm with the Bézout matrix
- Approximate greatest common divisor of several polynomials from Hankel matrices
- Approximate GCD by relaxed NewtonSLRA algorithm
- An Efficient Algorithm for Computing Parametric Multivariate Polynomial GCD
- An ODE-Based Method for Computing the Distance of Coprime Polynomials to Common Divisibility
- The calculation of the degree of an approximate greatest common divisor of two polynomials
- Approximate polynomial GCD over integers
- Blind image deconvolution through Bezoutians
- Recursive polynomial remainder sequence and its subresultants
- The ERES method for computing the approximate GCD of several polynomials
- Approximate polynomial GCD: small degree and small height perturbations
This page was built for publication: An algorithm for computing certified approximate GCD of \(n\) univariate polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1295792)
