Computing Nearest Gcd with Certification - Archive ouverte HAL Access content directly
Conference Papers Year : 2009

Computing Nearest Gcd with Certification

(1) , (1) , (2) , (2)
André Galligo
  • Function : Author
  • PersonId : 835184
Bernard Mourrain


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.
Fichier principal
Vignette du fichier
main.pdf (192.69 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00437559 , version 1 (30-11-2009)


  • 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⟩
398 View
198 Download


Gmail Facebook Twitter LinkedIn More