A Subdivision Method for Computing Nearest Gcd with Certification

Guillaume Chèze 1 André Galligo 2, 3 Bernard Mourrain 2 Jean-Claude Yakoubsohn 1
2 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : 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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2011, 412 (35), pp.4493-4503. 〈10.1016/j.tcs.2011.04.018〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00589062
Contributeur : Bernard Mourrain <>
Soumis le : mercredi 27 avril 2011 - 13:46:40
Dernière modification le : vendredi 14 septembre 2018 - 09:16:05
Document(s) archivé(s) le : jeudi 28 juillet 2011 - 02:42:45

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Guillaume Chèze, André Galligo, Bernard Mourrain, Jean-Claude Yakoubsohn. A Subdivision Method for Computing Nearest Gcd with Certification. Theoretical Computer Science, Elsevier, 2011, 412 (35), pp.4493-4503. 〈10.1016/j.tcs.2011.04.018〉. 〈inria-00589062〉

Partager

Métriques

Consultations de la notice

356

Téléchargements de fichiers

136