Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:









Author, Editor

Author(s):

Mehlhorn, Kurt
Sagraloff, Michael

dblp
dblp



Editor(s):





BibTeX Citekey*:

ACS-TR-361502-03

Language:

English

Title, Institution

Title*:

A deterministic Bitstream Descartes Algorithm

Institution*:

University of Groningen

Publishers or Institutions Address*:

9700 AB Groningen THE NETHERLANDS

Type:

Technical Report

No, Year, pp.,

Number*:

ACS-TR-361502-03

Pages*:

18

Month:


VG Wort
Pages*:

361502-03

Year*:

2008

ISBN/ISSN:






DOI:




Note, Abstract, ©

Note:

accepted to ISSAC 2009

(LaTeX) Abstract:

We describe a variant of the Descartes algorithm for root isolation of polynomials with real
coefficients. It is assumed that the coefficients of the polynomial can be approximated with arbitrary
precision; exact computation in the field of coefficients is not required. We refer to such
coefficients as bitstream coefficients. The algorithm is deterministic and has same asymptotic
complexity as the randomized bitstream Descartes algorithm of Eigenwillig et. al. [EKK+05].
Besides being deterministic, the algorithm is also somewhat simpler to analyse.

Categories / Keywords:


Copyright Message:


HyperLinks / References / URLs:

http://acs.cs.rug.nl/acstr/ACS-TR-361502-03.pdf

Personal Comments:


File Upload:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

MPG Subsubunit:

Geometric Computing

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:
@TECHREPORT{ACS-TR-361502-03,
AUTHOR = {Mehlhorn, Kurt and Sagraloff, Michael},
TITLE = {A deterministic Bitstream Descartes Algorithm},
YEAR = {2008},
TYPE = {Technical Report},
INSTITUTION = {University of Groningen},
NUMBER = {ACS-TR-361502-03},
PAGES = {18},
ADDRESS = {9700 AB Groningen THE NETHERLANDS},
NOTE = {accepted to ISSAC 2009},
}


Entry last modified by Kurt Mehlhorn, 04/15/2009
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)
Michael Sagraloff
Created
03/27/2009 10:31:01 AM
Revisions
3.
2.
1.
0.
Editor(s)
Kurt Mehlhorn
Michael Sagraloff
Michael Sagraloff
Michael Sagraloff
Edit Dates
04/15/2009 10:51:31 AM
03/27/2009 10:38:42 AM
03/27/2009 10:31:28 AM
03/27/2009 10:31:01 AM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section