Journal
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS
Volume 14, Issue 6, Pages 1117-1172Publisher
SPRINGER
DOI: 10.1007/s10208-014-9212-1
Keywords
Roadmaps; Real algebraic variety; Baby step-giant step
Funding
- National Science Foundation [CCF-0915954, CCF-1319080, DMS-1161629]
- French National Research Agency [ANR-09-BLAN-0371-01, ANR-2011-BS03-011-06]
- NSERC
- Canada Research Chairs Program
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1319080] Funding Source: National Science Foundation
Ask authors/readers for more resources
Let be a real closed field and an ordered domain. We present an algorithm that takes as input a polynomial and computes a description of a roadmap of the set of zeros, of Q in The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain is bounded by where As a consequence, there exist algorithms for computing the number of semialgebraically connected components of a real algebraic set, whose complexity is also bounded by where The best previously known algorithm for constructing a roadmap of a real algebraic subset of defined by a polynomial of degree d has complexity.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available