A numerical algorithm for zero counting, I: Complexity and accuracy

作者：Cucker, Felipe^*; Krick, Teresa; Malajovich, Gregorio; Wschebor, Mario

来源：Journal of Complexity, 2008, 24(5-6): 582-605.

DOI：10.1016/j.jco.2008.03.001

• Counting algorithms
• Polynomial systems
• Finite precision

We describe an algorithm to count the number of distinct real zeros of a polynomial (square) system f. The algorithm performs O(log(nDk(f))) iterations (grid refinements) where n is the number of polynomials (as well as the dimension of the ambient space), D is a bound on the polynomials' degree, and k(f) is a condition number for the system. Each iteration uses an exponential number of operations. The algorithm uses finite-precision arithmetic and a major feature of our results is a bound for the precision required to ensure that the returned output is correct which is polynomial in n and D and logarithmic in k(f). The algorithm parallelizes well in the sense that each iteration can be computed in parallel polynomial time in n, log D and log(k(f)).

• 出版日期2008-12
• 单位香港城市大学