Use of algebraically independent numbers for zero recognition of polynomial terms


Richardson, D. and El-Sonbaty, A., 2003. Use of algebraically independent numbers for zero recognition of polynomial terms. Journal of Complexity, 19 (5), pp. 631-637.

Related documents:

This repository does not currently have the full-text of this item.
You may be able to access a copy if URLs are provided below.


A polynomial term is a tree with operators *, +, - on the interior nodes and natural numbers and variables on the frontier. We attempt to decide whether or not such a tree represents the zero polynomial by substituting algebraically independent real numbers for the variables and attempting to decide whether or not the resulting constant is zero. From this we get a probabilistic zero recognition test which is somewhat more expensive computationally than the usual method of choosing random integers in a large interval and evaluating, but which depends on the ability to choose a random point in the unit cube and to approximate a polynomial at that point. We also state a conjecture about algebraic independence measure which would give us a deterministic test with a uniformly chosen test point. The result is that if a polynomial term has s(T) nodes, then the bit complexity of deterministic zero recognition is bounded by O(s(T)M(s(T) length(T))), where length(T) measures the length of the term T, and M(n) is the bit complexity of multiplication of two n-digit natural numbers.


Item Type Articles
CreatorsRichardson, D.and El-Sonbaty, A.
DepartmentsFaculty of Science > Computer Science
ID Code5515
Additional InformationID number: ISI:000185363300001


Actions (login required)

View Item