Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

URL of the conference:

http://gcoe.math.kyushu-u.ac.jp/ascm-macis2009/schedule_and_program.html

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 03:02:07 PM
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section