Numerical Computation of a Polynomial GCD and Extensions

Victor Y. Pan 1
1 SAFIR - Algebraic Formal Systems for Industry and Research
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In the first part of this paper, we define approximate polynomial gcds (greatest common divisors) and extended gcds provided that approximations to the zeros of the input polynomials are available. We relate our novel definition to the older and weaker ones, based on perturbation of the coefficients of the input polynomials, we demonstrate some deficiency of the latter definitions (which our definition avoids), and we propose new effective sequential and parallel (RNC and NC) algorithms for computing approximate gcds and extended gcds. Our stronger results are obtained with no increase of the asymptotic bounds on the computational cost. This is partly due to application of our recent nearly optimal algorithms for approximating polynomial zeros. In the second part of our paper, working under the older and more customary definition of approximate gcds, we modify and develop an alternative approach, which was previously based on the computation of the Singular Value Decomposition (SVD) of the associated Sylvester (resultant) matrix. We observe that only a small part of the SVD computation is needed in our case, and we also yield further simplification by using the techniques of Padé approximation and computations with Hankel and Bezout matrices. Finally, in the last part of our paper, we show an extension of the numerical computation of the gcd to the problem of computing numerical rank of a Hankel matrix, which is a bottleneck of Padé and Berlekamp-Massey computations, having important applications to coding and transmission of information.
Type de document :
RR-2969, INRIA. 1996
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:37:13
Dernière modification le : samedi 27 janvier 2018 - 01:31:31
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:06:25



  • HAL Id : inria-00073729, version 1



Victor Y. Pan. Numerical Computation of a Polynomial GCD and Extensions. RR-2969, INRIA. 1996. 〈inria-00073729〉



Consultations de la notice


Téléchargements de fichiers