Intrinsic near quadratic complexity bounds for real multivariate root counting. (English) Zbl 0929.65028
Bilardi, Gianfranco (ed.) et al., Algorithms - ESA ’98. 6th annual European symposium, Venice, Italy, August 24–26, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1461, 127-138 (1998).
Summary: We give a new algorithm, with three versions, for computing the number of real roots of a system of \(n\) polynomial equations in \(n\) unknowns. The first version is of Monte Carlo type and, neglecting logarithmic factors, runs in time quadratic in the average number of complex roots of a closely related system. The other two versions run nearly as fast and progressively remove a measure zero locus of failures present in the first version. Via a slight simplification of our algorithm, we can also count complex roots, with or without multiplicity, within the same complexity bounds. We also derive an even faster algorithm for the special case \(n= 2\), which may be of independent interest.
For the entire collection see [Zbl 0895.00050].
For the entire collection see [Zbl 0895.00050].
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 65Y20 | Complexity and performance of numerical algorithms |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
| 30C15 | Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) |
| 26C10 | Real polynomials: location of zeros |
