A Subdivision Method for Computing Nearest Gcd with Certification - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2011

A Subdivision Method for Computing Nearest Gcd with Certification

Résumé

A new subdivision method for computing the nearest univariate gcd is described and analyzed. It is based on an exclusion test and an inclusion test. The xclusion test in a cell exploits Taylor expansion of the polynomial at the center of the cell. The inclusion test uses Smale's alpha-theorems to certify the existence and unicity of a solution in a cell. Under the condition of simple roots for the distance minimization problem, we analyze the complexity of the algorithm in terms of a condition number, which is the inverse of the distance to the set of degenerate systems. We report on some experimentation on representative examples to illustrate the behavior of the algorithm.
Fichier principal
Vignette du fichier
paper.pdf (312.35 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00589062 , version 1 (27-04-2011)

Identifiants

Citer

Guillaume Chèze, André Galligo, Bernard Mourrain, Jean-Claude Yakoubsohn. A Subdivision Method for Computing Nearest Gcd with Certification. Theoretical Computer Science, 2011, 412 (35), pp.4493-4503. ⟨10.1016/j.tcs.2011.04.018⟩. ⟨inria-00589062⟩
377 Consultations
130 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More