de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45332

Sagraloff,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.