Skip to Main content Skip to Navigation
New interface
Journal articles

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 (1965 - 2019), 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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Bernard Mourrain Connect in order to contact the contributor
Submitted on : Wednesday, April 27, 2011 - 1:46:40 PM
Last modification on : Tuesday, October 25, 2022 - 11:58:10 AM
Long-term archiving on: : Thursday, July 28, 2011 - 2:42:45 AM


Files produced by the author(s)



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⟩



Record views


Files downloads