Electronic Journal Article
@Article
Zeitschriftenartikel in einem e-Journal



Show entries of:

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

Action:

login to update

Options:








Author, Editor

Author(s):

Sharma, Vikram

dblp



BibTeX cite key*:

Sharma2008

Title

Title*:

Complexity of real root isolation using continued fractions

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:

http://www.sciencedirect.com/science/journal/03043975

Download URL
for the article:

http://dx.doi.org/10.1016/j.tcs.2008.09.017

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.sciencedirect.com/

Publisher's
Address:


ISSN:


Vol, No, Year, pp.

Volume:

409

Number:


Month:


Year*:

2008

Pages:

292-310

Number of VG Pages:


Sequence Number:


DOI:

doi:10.1016/j.tcs.2008.09.017

Abstract, Links, (C)

Note:


(LaTeX) Abstract:

In this paper, we provide polynomial bounds on the worst case bit-complexity of
two formulations of the continued fraction algorithm.
In particular, for a square-free integer polynomial of degree $n$ with
coefficients of bit-length $L$, we show that the bit-complexity
of Akritas' formulation is $\wt{O}(n^8L^3)$, and the bit-complexity
of a formulation by Akritas and Strzebo\'nski is $\wt{O}(n^7L^2)$;
here $\wt{O}$ indicates that we are omitting logarithmic factors.
The analyses use a bound by Hong to compute
the floor of the smallest positive root of a polynomial, which is a crucial
step in the continued fraction algorithm. We also propose a modification
of the latter formulation that achieves a bit-complexity of $\wt{O}(n^5L^2)$.

URL for the Abstract:


Categories / Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

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:

@MISC{Sharma2008,
AUTHOR = {Sharma, Vikram},
TITLE = {Complexity of real root isolation using continued fractions},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2008},
VOLUME = {409},
PAGES = {292--310},
DOI = {doi:10.1016/j.tcs.2008.09.017},
}


Entry last modified by Vikram Sharma, 03/03/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)
Vikram Sharma
Created
01/09/2009 04:57:53 PM
Revision
0.



Editor
Vikram Sharma



Edit Date
01/09/2009 04:57:53 PM



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section