MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kerber, Michaeldblp
Editor(s):
Gerdt, Vladimir
Mayr, Ernst
Vorozhtsov, Evgenii		dblp
dblp
dblp
Not MPII Editor(s):
Gerdt, Vladimir
Mayr, Ernst
Vorozhtsov, Evgenii
BibTeX cite key*:
Kerber_CASC_2009
Title, Booktitle
Title*:
On the Complexity of Reliable Root Approximation
k-otcorra-09-authprep.pdf (126.26 KB)
Booktitle*:
Computer Algebra in Scientific Computing : 11th International Workshop, CASC 2009
Event, URLs
Conference URL::
http://www14.in.tum.de/CASC2009/
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-04103-7_15
Event Address*:
Kobe, Japan
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
13 September 2009
Event End Date:
17 September 2009
Publisher
Name*:
Springer
URL:
www.springerlink.com
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
5743
Number:
Month:
Pages:
155-167
Year*:
2009
VG Wort Pages:
ISBN/ISSN:
978-3-642-04102-0
Sequence Number:
DOI:
10.1007/978-3-642-04103-7_15
Note, Abstract, ©
(LaTeX) Abstract:
This work addresses the problem of computing a certified ε-approximation of all real roots of a square-free integer polynomial. We proof an upper bound for its bit complexity, by analyzing an algorithm that first computes isolating intervals for the roots, and subsequently refines them using Abbott’s Quadratic Interval Refinement method. We exploit the eventual quadratic convergence of the method. The threshold for an interval width with guaranteed quadratic convergence speed is bounded by relating it to well-known algebraic quantities.
Keywords:
Real Root Isolation, Quadratic Interval Refinement, Root Approximation
Copyright Message:
© Springer, 2009. The original publication is available at www.springerlink.com
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{Kerber_CASC_2009,
AUTHOR = {Kerber, Michael},
 EDITOR = {Gerdt, Vladimir and Mayr, Ernst and Vorozhtsov, Evgenii},
 TITLE = {On the Complexity of Reliable Root Approximation},
 BOOKTITLE = {Computer Algebra in Scientific Computing : 11th International Workshop, CASC 2009},
 PUBLISHER = {Springer},
 YEAR = {2009},
 VOLUME = {5743},
 PAGES = {155--167},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Kobe, Japan},
 ISBN = {978-3-642-04102-0},
 DOI = {10.1007/978-3-642-04103-7_15},
}

Entry last modified by Anja Becker, 03/08/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/05/2010 10:33:47
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Michael Kerber
Michael Kerber

Edit Dates
08.03.2010 13:55:44
01/05/2010 10:34:10 AM
01/05/2010 10:33:47 AM

File Attachment Icon
k-otcorra-09-authprep.pdf