MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Eigenwillig, Arno
Kettner, Lutz
Krandick, Werner
Mehlhorn, Kurt
Schmitt, Susanne
Wolpert, Nicola		dblp
dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Krandick, Werner
Editor(s):
Ganzha, Viktor G.
Mayr, Ernst W.
Vorozhtsov, Evgenii V.		dblp
dblp
dblp
BibTeX cite key*:
Eigenwillig2005
Title, Booktitle
Title*:
A Descartes algorithm for polynomials with bit-stream coefficients
Booktitle*:
Computer Algebra in Scientific Computing : 8th International Workshop, CASC 2005
Event, URLs
Conference URL::
http://www.cargo.wlu.ca/casc2005/
Downloading URL:
http://www.springerlink.com/content/57wg2fn0ud4q7edp/fulltext.pdf
Event Address*:
Kalamata, Greece
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
12 September 2005
Event End Date:
16 September 2005
Publisher
Name*:
Springer
URL:
http://www.springer.com
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3718
Number:
Month:
Pages:
138-149
Year*:
2005
VG Wort Pages:
32
ISBN/ISSN:
3-540-28966-6
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite) bit-streams. In other words, coefficients can be approximated to any desired accuracy, but are not known exactly. We show that a variant of the Descartes algorithm can cope with bit-stream coefficients. To isolate the real roots of a square-free real polynomial with root separation ρ, coefficients and , it needs coefficient approximations to O(n(log(1/ρ) + τ)) bits after the binary point and has an expected cost of O(n4 (log(1/ρ) + τ)2) bit operations.
URL for the Abstract:
http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1007/11555964_12
http://www.springerlink.com/content/57wg2fn0ud4q7edp/
HyperLinks / References / URLs:
http://dblp.uni-trier.de/db/conf/casc/casc2005.html#EigenwilligKKMSW05
Download
Access Level:
Previledged Users

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{Eigenwillig2005,
AUTHOR = {Eigenwillig, Arno and Kettner, Lutz and Krandick, Werner and Mehlhorn, Kurt and Schmitt, Susanne and Wolpert, Nicola},
 EDITOR = {Ganzha, Viktor G. and Mayr, Ernst W. and Vorozhtsov, Evgenii V.},
 TITLE = {A Descartes algorithm for polynomials with bit-stream coefficients},
 BOOKTITLE = {Computer Algebra in Scientific Computing : 8th International Workshop, CASC 2005},
 PUBLISHER = {Springer},
 YEAR = {2005},
 VOLUME = {3718},
 PAGES = {138--149},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Kalamata, Greece},
 ISBN = {3-540-28966-6},
}

Entry last modified by Christine Kiesel, 12/11/2006
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)
Anja Becker		Created
10/06/2005 12:48:23
Revisions
12.
11.
10.
9.
8.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
11.12.2006 15:59:32
11.12.2006 10:32:28
09.11.2006 11:31:22
09.11.2006 11:30:31
03.11.2006 10:02:21