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 PM
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