MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Sagraloff, Michael
Kerber, Michael
Hemmer, Michael		dblp
dblp
dblp
Editor(s):
Suzuki, Masakazu
Hong, Hoon
Anai, Hirokazu
Yap, Chee
Sato, Yosuke
Yoshida, Hiroshi		dblp
dblp
dblp
dblp
dblp
dblp
Not MPII Editor(s):
Suzuki, Masakazu
Hong, Hoon
Anai, Hirokazu
Yap, Chee
Sato, Yosuke
Yoshida, Hiroshi
BibTeX cite key*:
SKH-CCRI-2009
Title, Booktitle
Title*:
Certified Complex Root Isolation via Adaptive Root Separation Bounds
Booktitle*:
The Joint Conference of ASCM 2009 and MACIS 2009
Event, URLs
Conference URL::
http://gcoe.math.kyushu-u.ac.jp/ascm-macis2009/schedule_and_program.html
Downloading URL:
Event Address*:
Fukuoka, Japan
Language:
English
Event Date*
(no longer used):
Organization:
Math-for-Industry (MI)
Event Start Date:
14 December 2009
Event End Date:
17 December 2009
Publisher
Name*:
COE
URL:
http://www.gcoe-mi.jp/
Address*:
Fukuoka, Japan
Type:
Vol, No, Year, pp.
Series:
MI Lecture Note Series
Volume:
22
Number:
Month:
December
Pages:
151-166
Year*:
2009
VG Wort Pages:
15
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{SKH-CCRI-2009,
AUTHOR = {Sagraloff, Michael and Kerber, Michael and Hemmer, Michael},
 EDITOR = {Suzuki, Masakazu and Hong, Hoon and Anai, Hirokazu and Yap, Chee and Sato, Yosuke and Yoshida, Hiroshi},
 TITLE = {Certified Complex Root Isolation via Adaptive Root Separation Bounds},
 BOOKTITLE = {The Joint Conference of ASCM 2009 and MACIS 2009},
 PUBLISHER = {COE},
 YEAR = {2009},
 ORGANIZATION = {Math-for-Industry (MI)},
 VOLUME = {22},
 PAGES = {151--166},
 SERIES = {MI Lecture Note Series},
 ADDRESS = {Fukuoka, Japan},
 MONTH = {December},
 ISBN = {1881-4042},
}

Entry last modified by Anja Becker, 03/09/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
01/25/2010 15:02:07
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Michael Hemmer
Michael Hemmer

Edit Dates
09.03.2010 14:38:42
01/25/2010 03:21:06 PM
01/25/2010 03:02:07 PM