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.
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/inria-00589062
Contributor : Bernard Mourrain <>
Submitted on : Wednesday, April 27, 2011 - 1:46:40 PM
Last modification on : Thursday, October 17, 2019 - 8:52:16 AM
Long-term archiving on : Thursday, July 28, 2011 - 2:42:45 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

600

Files downloads

269