Almost tight recursion tree bounds for the descartes method

Arno Eigenwillig; Vikram Sharma; Chee K. Yap

doi:10.1145/1145768.1145786

Almost tight recursion tree bounds for the descartes method

Arno Eigenwillig, Vikram Sharma, Chee K. Yap

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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) = ∑_i=0 ⁿ a_iXⁱ with integer coefficients |a _i| < 2^L, this yields a bound of O(n(L + logn)) on the size of recursion trees. We show that this bound is tight for L = Ω(log n), and we use it to derive the best known bit complexity bound for the integer case.

Original language	English (US)
Title of host publication	Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC 2006
Publisher	Association for Computing Machinery (ACM)
Pages	71-78
Number of pages	8
ISBN (Print)	1595932763, 9781595932761
DOIs	https://doi.org/10.1145/1145768.1145786
State	Published - 2006
Event	International Symposium on Symbolic and Algebraic Computation, ISSAC 2006 - Genova, Italy Duration: Jul 9 2006 → Jul 12 2006

Publication series

Name	Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
Volume	2006

Other

Other	International Symposium on Symbolic and Algebraic Computation, ISSAC 2006
Country/Territory	Italy
City	Genova
Period	7/9/06 → 7/12/06

Keywords

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

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1145/1145768.1145786

Cite this

Eigenwillig, A., Sharma, V., & Yap, C. K. (2006). Almost tight recursion tree bounds for the descartes method. In Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC 2006 (pp. 71-78). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1145768.1145786

Almost tight recursion tree bounds for the descartes method. / Eigenwillig, Arno; Sharma, Vikram; Yap, Chee K.
Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC 2006. Association for Computing Machinery (ACM), 2006. p. 71-78 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC; Vol. 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Eigenwillig, A, Sharma, V & Yap, CK 2006, Almost tight recursion tree bounds for the descartes method. in Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC 2006. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, vol. 2006, Association for Computing Machinery (ACM), pp. 71-78, International Symposium on Symbolic and Algebraic Computation, ISSAC 2006, Genova, Italy, 7/9/06. https://doi.org/10.1145/1145768.1145786

Eigenwillig A, Sharma V, Yap CK. Almost tight recursion tree bounds for the descartes method. In Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC 2006. Association for Computing Machinery (ACM). 2006. p. 71-78. (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). doi: 10.1145/1145768.1145786

@inproceedings{981e2c348a884d4a8c97bcfbda12e5b7,

title = "Almost tight recursion tree bounds for the descartes method",

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) = ∑i=0 n aiXi with integer coefficients |a i| < 2L, this yields a bound of O(n(L + logn)) on the size of recursion trees. We show that this bound is tight for L = Ω(log n), and we use it to derive the best known bit complexity bound for the integer case.",

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

author = "Arno Eigenwillig and Vikram Sharma and Yap, {Chee K.}",

year = "2006",

doi = "10.1145/1145768.1145786",

language = "English (US)",

isbn = "1595932763",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

publisher = "Association for Computing Machinery (ACM)",

pages = "71--78",

booktitle = "Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC 2006",

address = "United States",

note = "International Symposium on Symbolic and Algebraic Computation, ISSAC 2006 ; Conference date: 09-07-2006 Through 12-07-2006",

}

TY - GEN

T1 - Almost tight recursion tree bounds for the descartes method

AU - Eigenwillig, Arno

AU - Sharma, Vikram

AU - Yap, Chee K.

PY - 2006

Y1 - 2006

N2 - 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) = ∑i=0 n aiXi with integer coefficients |a i| < 2L, this yields a bound of O(n(L + logn)) on the size of recursion trees. We show that this bound is tight for L = Ω(log n), and we use it to derive the best known bit complexity bound for the integer case.

AB - 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) = ∑i=0 n aiXi with integer coefficients |a i| < 2L, this yields a bound of O(n(L + logn)) on the size of recursion trees. We show that this bound is tight for L = Ω(log n), and we use it to derive the best known bit complexity bound for the integer case.

KW - Bernstein basis

KW - Davenport-Mahler bound

KW - Descartes method

KW - Descartes rule of signs

KW - Polynomial real root isolation

UR - http://www.scopus.com/inward/record.url?scp=33748959696&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748959696&partnerID=8YFLogxK

U2 - 10.1145/1145768.1145786

DO - 10.1145/1145768.1145786

M3 - Conference contribution

AN - SCOPUS:33748959696

SN - 1595932763

SN - 9781595932761

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 71

EP - 78

BT - Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC 2006

PB - Association for Computing Machinery (ACM)

T2 - International Symposium on Symbolic and Algebraic Computation, ISSAC 2006

Y2 - 9 July 2006 through 12 July 2006

ER -

Almost tight recursion tree bounds for the descartes method

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this