# Item

ITEM ACTIONSEXPORT

Released

Paper

#### On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection

##### Locator

There are no locators available

##### Fulltext (public)

arXiv:1604.08944.pdf

(Preprint), 498KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Brand, C., & Sagraloff, M. (2016). On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection. Retrieved from http://arxiv.org/abs/1604.08944.

Cite as: http://hdl.handle.net/11858/00-001M-0000-002B-02AF-7

##### Abstract

Given a zero-dimensional polynomial system consisting of n integer
polynomials in n variables, we propose a certified and complete method to
compute all complex solutions of the system as well as a corresponding
separating linear form l with coefficients of small bit size. For computing l,
we need to project the solutions into one dimension along O(n) distinct
directions but no further algebraic manipulations. The solutions are then
directly reconstructed from the considered projections. The first step is
deterministic, whereas the second step uses randomization, thus being
Las-Vegas.
The theoretical analysis of our approach shows that the overall cost for the
two problems considered above is dominated by the cost of carrying out the
projections. We also give bounds on the bit complexity of our algorithms that
are exclusively stated in terms of the number of variables, the total degree
and the bitsize of the input polynomials.