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):

Kerber, Michael

dblp



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

URL of the conference:

http://www14.in.tum.de/CASC2009/

URL for downloading the paper:

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
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/05/2010 10:33:47 AM
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

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

View attachments here:


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