A numerical algorithm for zero counting. I: Complexity and accuracy (Q958246)

The authors present an algorithm that counts the number of distinct real zeros of a polynomial square system \(f\). The algorithm performs \({\mathcal O}(\log(n\cdot D\cdot k(f)))\), where \(n\) is the number of polynomials, \(D\) is a bound on the polynomials' degree, and \(k(f)\) is a condition number of the system. The algorithm uses finite-precision arithmetic and a major feature of the results is a bound for the precision required to ensure that the returned output is correct which is polynomial in \(n, D\), and logaritmic in \(k(f)\). Each iteration, that uses an exponential number of operations, can be computed in parallel polynomial time in \(n\), \(\log(D)\), and \(\log(k(f))\).