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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

16 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)582-605
Journal / PublicationJournal of Complexity
Volume24
Issue number5-6
Publication statusPublished - Oct 2008

Abstract

We describe an algorithm to count the number of distinct real zeros of a polynomial (square) system f. The algorithm performs O (log (n D κ (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 κ (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 κ (f). The algorithm parallelizes well in the sense that each iteration can be computed in parallel polynomial time in n, log D and log (κ (f)). © 2008 Elsevier Inc. All rights reserved.

Research Area(s)

  • Counting algorithms, Finite precision, Polynomial systems

Citation Format(s)

A numerical algorithm for zero counting, I : Complexity and accuracy. / Cucker, Felipe; Krick, Teresa; Malajovich, Gregorio; Wschebor, Mario.

In: Journal of Complexity, Vol. 24, No. 5-6, 10.2008, p. 582-605.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review