Electronic Proceedings Article
@InProceedings
Internet-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
Sharma, Vikram
Yap, Chee K.

dblp
dblp
dblp

Not MPG Author(s):

Sharma, Vikram
Yap, Chee K.

Editor(s):

Dumas, Jean-Guillaume

dblp

Not MPII Editor(s):

Dumas, Jean-Guillaume

BibTeX cite key*:

Eigenwillig2006a

Title, Conference

Title*:

Almost Tight Recursion Tree Bounds for the Descartes Method


ESY-DescTree-ISSAC06-authprep.pdf (183.17 KB)

Booktitle*:

ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

Event Address*:

Genova, Italy

URL of the conference:

http://issac2006.dima.unige.it/

Event Date*:
(no longer used):


URL for downloading the paper:

http://doi.acm.org/10.1145/1145768.1145786

Event Start Date:

9 July 2006

Event End Date:

12 July 2006

Language:

English

Organization:

Association for Computing Machinery (ACM)

Publisher

Publisher's Name:

ACM

Publisher's URL:

http://www.acm.org/

Address*:

New York, USA

Type:


Vol, No, pp., Year

Series:


Volume:


Number:


Month:

July

Pages:

71-78



Sequence Number:


Year*:

2006

ISBN/ISSN:

1-59593-276-3





Abstract, Links, ©

URL for Reference:


Note:


(LaTeX) Abstract:

We give a unified ("basis free") framework for the Descartes method for real root isolation of square-free real polynomials. This framework encompasses the usual Descartes' rule of sign method for polynomials in the power basis as well as its analog in the Bernstein basis. We then give a new bound on the size of the recursion tree in the Descartes method for polynomials with real coefficients. Applied to polynomials $A(X) = \sum_{i=0}^n a_iX^i$ with integer coefficients $\abs{a_i} < 2^L$, this yields a bound of $O(n(L + \log n))$ on the size of recursion trees. We show that this bound is tight for $L = \Omega(\log n)$, and we use it to derive the best known bit complexity bound for the integer case.

URL for the Abstract:




Tags, Categories, Keywords:

Polynomial real root isolation, Descartes method, Descartes rule of signs, Bernstein basis, Davenport-Mahler bound

HyperLinks / References / URLs:

http://doi.acm.org/10.1145/1145768.1145786

Copyright Message:

Copyright (c) ACM, 2006. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation (ISSAC 2006), http://doi.acm.org/10.1145/1145768.1145786

Personal Comments:

The title on the printed proceedings volume is "...and Algebraic Computations", but according to (i) grammar, (ii) previous proceedings volumes, and (iii) the ACM Digital Library, the final "s" is wrong and should be deleted.

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{Eigenwillig2006a,
AUTHOR = {Eigenwillig, Arno and Sharma, Vikram and Yap, Chee K.},
EDITOR = {Dumas, Jean-Guillaume},
TITLE = {Almost Tight Recursion Tree Bounds for the {D}escartes Method},
BOOKTITLE = {ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation},
PUBLISHER = {ACM},
YEAR = {2006},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {71--78},
ADDRESS = {Genova, Italy},
MONTH = {July},
ISBN = {1-59593-276-3},
}


Entry last modified by Uwe Brahm, 04/27/2007
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)
Arno Eigenwillig
Created
07/21/2006 01:46:07 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Uwe Brahm
Arno Eigenwillig
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
2007-04-27 18:33:58
03/17/2007 05:26:19 PM
07.02.2007 11:23:34
07.02.2007 11:22:43
07/21/2006 01:47:15 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
ESY-DescTree-ISSAC06-authprep.pdf