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:








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

URL of the conference:

http://www.cargo.wlu.ca/casc2005/

URL for downloading the paper:

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