Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Krandick, Werner
Mehlhorn, Kurt

dblp
dblp

Not MPG Author(s):

Krandick, Werner

BibTeX cite key*:

mehlhorn06e

Title

Title*:

New bounds for the Descartes method


Mehlhorn_a_2006_e.pdf (492.02 KB)

Journal

Journal Title*:

Journal of Symbolic Computation

Journal's URL:


Download URL
for the article:

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6WM7-4HJRRSD-1-1&_cdi=6927&_user=43521&_orig=search&_coverDate=01%2F31%2F2006&_sk=999589998&view=c&_alid=449193459&_rdoc=1&wchp=dGLbVtb-zSkWW&md5=9b7550f150e3c3174b33f31c1520a947&ie=/sdarticle.pdf

Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

41

Number:

1

Publishing Date:

2006

Pages*:

49-66

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:


We give a new bound for the number of recursive subdivisions in the Descartes method for polynomial real root isolation. Our proof uses Ostrowski’s theory of normal power series from 1950 which has so far been overlooked in the literature. We combine Ostrowski’s results with a theorem of Davenport from 1985 to obtain our bound. We also characterize normality of cubic polynomials by explicit conditions on their roots and derive a generalization of one of Ostrowski’s theorems.

URL for the Abstract:


Categories,
Keywords:

Polynomial real root isolation, Descartes rule of signs, Modified Uspensky method, Recursion tree analysis, Normal polynomials, Root separation bounds, History of mathematics, Möbius transformations, Coefficient sign variations, Cylindrical algebraic decomposition

HyperLinks / References / URLs:

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WM7-4HJRRSD-1&_user=43521&_coverDate=01%2F31%2F2006&_alid=449193459&_rdoc=1&_fmt=summary&_orig=search&_cdi=6927&_sort=d&_docanchor=&view=c&_acct=C000004638&_version=1&_urlVersion=0&_userid=43521&md5=b776dd8aa1e61ad5754d4e3cf1e4b63f

Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

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


BibTeX Entry:

@ARTICLE{mehlhorn06e,
AUTHOR = {Krandick, Werner and Mehlhorn, Kurt},
TITLE = {New bounds for the Descartes method},
JOURNAL = {Journal of Symbolic Computation},
YEAR = {2006},
NUMBER = {1},
VOLUME = {41},
PAGES = {49--66},
}


Entry last modified by Uwe Brahm, 04/26/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)
Christine Kiesel
Created
08/09/2006 01:58:59 PM
Revisions
11.
10.
9.
8.
7.
Editor(s)
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
2007-04-26 18:56:11
04.10.2006 06:25:31
04.10.2006 06:22:14
20.09.2006 17:12:17
14.09.2006 09:02:26
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_a_2006_e.pdf
View attachments here: