Skip to Main content Skip to Navigation
Conference papers

Computing Nearest Gcd with Certification

Guillaume Chèze 1 Jean-Claude Yakoubsohn 1 André Galligo 2 Bernard Mourrain 2
2 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis (... - 2019), CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : A bisection method, based on exclusion and inclusion tests, is used to address the nearest univariate gcd problem formulated as a bivariate real minimization problem of a rational fraction. The paper presents an algorithm, a first implementation and a complexity analysis relying on Smale's $\alpha$-theory. We report its behavior on an illustrative example.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Bernard Mourrain Connect in order to contact the contributor
Submitted on : Monday, November 30, 2009 - 10:01:22 PM
Last modification on : Tuesday, December 7, 2021 - 4:04:11 PM
Long-term archiving on: : Thursday, June 17, 2010 - 10:51:43 PM


Files produced by the author(s)


  • HAL Id : inria-00437559, version 1


Guillaume Chèze, Jean-Claude Yakoubsohn, André Galligo, Bernard Mourrain. Computing Nearest Gcd with Certification. International Workshop Symbolic-Numeric Computation (SNC), Aug 2009, Kyoto, Japan. pp.29-34. ⟨inria-00437559⟩



Record views


Files downloads