English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Certified Complex Root Isolation via Adaptive Root Separation Bounds

MPS-Authors
/persons/resource/persons45332

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

/persons/resource/persons44759

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

/persons/resource/persons44609

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Sagraloff, M., Kerber, M., & Hemmer, M. (2009). Certified Complex Root Isolation via Adaptive Root Separation Bounds. In M. Suzuki, H. Hong, H. Anai, C. Yap, Y. Sato, & H. Yoshida (Eds.), 9th Asian Symposium on Computational Mathematics (ASCM) (pp. 151-166). Fukuoka: COE.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1819-6
Abstract
We address the problem of {\em root isolation} for polynomial systems: for an affine, zero-dimensional polynomial system of $N$ equations in $N$ variables, we describe an algorithm to encapsulate all complex solutions into disjoint regions, each containing precisely one solution (called \emph{isolating regions}). Our approach also computes the multiplicity of each solution. The main novelty is a new approach to certify that a set of computed regions is indeed isolating. It is based on an adaptive root separation bound obtained from combining information about the approximate location of roots and resultant calculus. Here we use simple subdivision method to determine the number of roots within certain regions. The resultant calculus only takes place over prime fields to avoid the disadvantageous coefficient growth in symbolic methods, without sacrificing the exactness of the output. The presented approach is complete for uni- and bivariate systems, and in general applies in higher dimensions as well, possibly after a coordinate change.