A Baby Step–Giant Step Roadmap Algorithm for General Algebraic SetsReportar como inadecuado




A Baby Step–Giant Step Roadmap Algorithm for General Algebraic Sets - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Purdue University West Lafayette 2 IRMAR - Institut de Recherche Mathématique de Rennes 3 PolSys - Polynomial Systems LIP6 - Laboratoire d-Informatique de Paris 6, Inria Paris-Rocquencourt 4 Computer Science Department, University of Western Ontario Computer Science Department

Abstract : Let R be a real closed field and D ⊂ R an ordered domain. We give an algorithm that takes as input a polynomial Q ∈ DX 1 , . . . , X k , and computes a description of a roadmap of the set of zeros, ZerQ, R k, of Q in R k . The complexity of the algorithm, measured by the number of arithmetic opera-tions in the ordered domain D, is bounded by d Ok √ k , where d = degQ ≥ 2. As a consequence, there exist algorithms for computing the number of semi-algebraically connected components of a real algebraic set, ZerQ, R k, whose complexity is also bounded by d Ok √ k , where d = degQ ≥ 2. The best pre-viously known algorithm for constructing a roadmap of a real algebraic subset of R k defined by a polynomial of degree d has complexity d Ok 2 .

Keywords : Roadmaps Real algebraic variety Baby step-giant step





Autor: Saugata Basu - Marie-Françoise Roy - Mohab Safey El Din - Eric Schost -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados