کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4609179 | 1631474 | 2008 | 24 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A numerical algorithm for zero counting, I: Complexity and accuracy A numerical algorithm for zero counting, I: Complexity and accuracy](/preview/png/4609179.png)
We describe an algorithm to count the number of distinct real zeros of a polynomial (square) system ff. The algorithm performs O(log(nDκ(f))) iterations (grid refinements) where nn is the number of polynomials (as well as the dimension of the ambient space), D is a bound on the polynomials’ degree, and κ(f)κ(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 nn and D and logarithmic in κ(f)κ(f). The algorithm parallelizes well in the sense that each iteration can be computed in parallel polynomial time in nn, logD and log(κ(f))log(κ(f)).
Journal: Journal of Complexity - Volume 24, Issues 5–6, October–December 2008, Pages 582–605