Advertisement
Published in:
01-12-2014
A Baby Step–Giant Step Roadmap Algorithm for General Algebraic Sets
Published in: Foundations of Computational Mathematics | Issue 6/2014
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Let \(\mathrm {R}\) be a real closed field and \(\mathrm{D}\subset \mathrm {R}\) an ordered domain. We present an algorithm that takes as input a polynomial \(Q \in \mathrm{D}[X_{1},\ldots ,X_{k}]\) and computes a description of a roadmap of the set of zeros, \(\mathrm{Zer}(Q,\,\mathrm {R}^{k}),\) of Q in \(\mathrm {R}^{k}.\) The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain \(\mathrm{D},\) is bounded by \(d^{O(k \sqrt{k})},\) where \(d = \deg (Q)\ge 2.\) As a consequence, there exist algorithms for computing the number of semialgebraically connected components of a real algebraic set, \(\mathrm{Zer}(Q,\,\mathrm {R}^{k}),\) whose complexity is also bounded by \(d^{O(k \sqrt{k})},\) where \(d = \deg (Q)\ge 2.\) The best previously known algorithm for constructing a roadmap of a real algebraic subset of \(\mathrm {R}^{k}\) defined by a polynomial of degree d has complexity \(d^{O(k^{2})}.\)