More Web Proxy on the site http://driver.im/

Article

High-performance implementations of the Descartes method

Authors:

Jeremy R. Johnson,

Werner Krandick,

David G. Richardson,

Anatole D. RuslanovAuthors Info & Claims

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

Pages 154 - 161

https://doi.org/10.1145/1145768.1145797

Published: 09 July 2006 Publication History

Abstract

The Descartes method for polynomial real root isolation can be performed with respect to monomial bases and with respect to Bernstein bases. The first variant uses Taylor shift by 1 as its main subalgorithm, the second uses de Casteljau's algorithm. When applied to integer polynomials, the two variants have co-dominant, almost tight computing time bounds. Implementations of either variant can obtain speed-ups over previous state-of-the-art implementations by more than an order of magnitude if they use features of the processor architecture. We present an implementation of the Bernstein-bases variant of the Descartes method that automatically generates architecture-aware high-level code and leaves further optimizations to the compiler. We compare the performance of our implementation, algorithmically tuned implementations of the monomial and Bernstein variants, and architecture-unaware implementations of both variants on four different processor architectures and for three classes of input polynomials.

References

[1]

AMD. AMD Eighth-Generation Processor Architecture. http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/Hammer_architecture_WP_2.pdf, October 2001.

[2]

AMD. Processor Reference. http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/23932.pdf, June 2004.

[3]

AMD. Software Optimization Guide for AMD64 Processors, September 2005.

[4]

Alin Bostan, Philippe Flajolet, Bruno Salvy, and Éric Schost. Fast computation of special resultants. Journal of Symbolic Computation, 41(1):1--29, 2006.

Digital Library

[5]

George E. Collins and Alkiviadis G. Akritas. Polynomial real root isolation using Descartes' rule of signs. In R. D. Jenks, editor, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, pages 272--275. ACM Press, 1976.

Digital Library

[6]

George E. Collins et al. SACLIB User's Guide. Technical Report 93-19, Research Institute for Symbolic Computation, RISC-Linz, Johannes Kepler University, A-4040 Linz, Austria, 1993.

[7]

Intel Corporation. A Detailed Look Inside the Intel NetBurst Micro-Architecture of the Intel Pentium 4 Processor, November 2000.

[8]

Intel Corporation. The IA-32 Intel Architecture Optimization: Reference Manual, 2004.

[9]

Intel Corporation. Intel Pentium D Processor 800 Sequence: Datasheet, 2006.

[10]

Arno Eigenwillig, Vikram Sharma, and Chee K. Yap. Almost tight recursion tree bounds for the Descartes method. In J.-G. Dumas, editor, International Symposium on Symbolic and Algebraic Computation. ACM Press, 2006. To appear.

Digital Library

[11]

I. Z. Emiris, B. Mourrain, and E. Tsigaridas. Real algebraic numbers: Complexity analysis and experimentations. Research Report 5897, INRIA, 2006.

[12]

Gerald Farin. Curves and Surfaces for Computer Aided Geometric Design. Academic Press, 1988.

Digital Library

[13]

Jürgen Gerhard. Modular Algorithms in Symbolic Summation and Symbolic Integration, volume 3218 of Lecture Notes in Computer Science. Springer-Verlag, 2004.

Digital Library

[14]

Torbjörn Granlund. GNU MP: The GNU Multiple Precision Arithmetic Library. Swox AB, September 2004. Edition 4.1.4.

[15]

Torbjörn Granlund. GNU MP: The GNU Multiple Precision Arithmetic Library. Swox AB, March 2006. Edition 4.2.

[16]

Guillaume Hanrot, Fabrice Rouillier, Paul Zimmermann, and Sylvain Petitjean. Uspensky's algorithm. http://www.loria.fr/equipes/vegas/qi/usp/usp.c, 2004.

[17]

Tim Horel and Gary Lauterbach. UltraSPARC-III: Designing third-generation 64-bit performance. IEEE MICRO, 19(3):73--85, 1999.

Digital Library

[18]

International Standards Organization, http://www.iso.org. ISO/IEC 14882:2003: Programming languages-C++, 2003.

[19]

J. R. Johnson. Algorithms for Polynomial Real Root Isolation. Technical research report OSU-CISRC-8/91-TR21, The Ohio State University, Department of Computer and Information Science, 1991.

[20]

J. R. Johnson. Algorithms for polynomial real root isolation. In B. F. Caviness and J. R. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, pages 269--299. Springer-Verlag, 1998.

[21]

Jeremy R. Johnson, Werner Krandick, and Anatole D. Ruslanov. Architecture-aware classical Taylor shift by 1. In M. Kauers, editor, International Symposium on Symbolic and Algebraic Computation, pages 200--207. ACM Press, 2005.

Digital Library

[22]

Werner Krandick. Isolierung reeller Nullstellen von Polynomen. In J. Herzberger, editor, Wissenschaftliches Rechnen, pages 105--154. Akademie Verlag, Berlin, 1995.

[23]

Werner Krandick and Kurt Mehlhorn. New bounds for the Descartes method. Journal of Symbolic Computation, 41(1):49--66, 2006.

Digital Library

[24]

Jeffrey M. Lane and R. F. Riesenfeld. Bounds on a polynomial. BIT, 21(1):112--117, 1981.

[25]

B. Mourrain, J. P. Pavone, P. Trébuchet, and E. Tsigaridas. SYNAPS: A library for symbolic-numeric computation. Software presentation. MEGA 2005, Sardinia, Italy, May 2005. http://www-sop.inria.fr/galaad/logiciels/synaps/.

[26]

Bernard Mourrain, Fabrice Rouillier, and Marie-Françoise Roy. The Bernstein basis and real root isolation. In J. E. Goodman, J. Pach, and E. Welzl, editors, Combinatorial and Computational Geometry, volume 52 of Mathematical Sciences Research Institute Publications, pages 459--478. Cambridge University Press, 2005.

[27]

Fabrice Rouillier and Paul Zimmermann. Efficient isolation of a polynomial's real roots. Journal of Computational and Applied Mathematics, 162:33--50, 2004.

Digital Library

[28]

Victor Shoup. NTL: A Library for Doing Number Theory. http://www.shoup.net/ntl.

[29]

Victor Shoup. A new polynomial factorization algorithm and its implementation. Journal of Symbolic Computation, 20(4):363--397, 1995.

Digital Library

[30]

Bjarne Stroustrup. The C++ Standard: Incorporating Technical Corrigendum No. 1. John Wiley and Sons, 2003.

[31]

Sun Microsystems. Sun Studio Collection. http://www.sun.com/software/products/studio/.

[32]

Sun Microsystems. UltraSPARC III Cu: User's Manual, 2004.

[33]

Joachim von zur Gathen and Jürgen Gerhard. Fast algorithms for Taylor shifts and certain difference equations. In W. W. Küchlin, editor, International Symposium on Symbolic and Algebraic Computation, pages 40--47. ACM Press, 1997.

Digital Library

[34]

Larry Wall, Tom Christiansen, and Jon Orwant. Programming Perl. O'Reilly, 3rd edition, 2000.

Digital Library

Cited By

Ergür ATonelli-Cueto JTsigaridas EMaza MZhi L(2022)Beyond Worst-Case Analysis for Root Isolation AlgorithmsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535475(139-148)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535475
Dai LFan ZXia BZhang H(2019)Logcf: An Efficient Tool for Real Root IsolationJournal of Systems Science and Complexity10.1007/s11424-019-7361-732:6(1767-1782)Online publication date: 14-Dec-2019
https://doi.org/10.1007/s11424-019-7361-7
Johnson J(2012)In MemoriamACM Communications in Computer Algebra10.1145/2338496.233850446:1/2(52-54)Online publication date: 23-Jul-2012
https://dl.acm.org/doi/10.1145/2338496.2338504
Show More Cited By

Index Terms

High-performance implementations of the Descartes method

Recommendations

Almost tight recursion tree bounds for the Descartes method
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

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 ...
New bounds for the Descartes method

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 ...
Complexity of real root isolation using continued fractions
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

The efficiency of the continued fraction algorithm for isolating the real roots of a univariate polynomial depends upon computing tight lower bounds on the smallest positive root of a polynomial. The known complexity bounds for the algorithm rely on the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2006

374 pages

ISBN:1595932763

DOI:10.1145/1145768

General Chair:
Barry Trager
IBM T.J. Watson Research Center, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC06

Sponsor:

ISSAC06: International Symposium on Symbolic and Algebraic Computation

July 9 - 12, 2006

Genoa, Italy

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
245
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ergür ATonelli-Cueto JTsigaridas EMaza MZhi L(2022)Beyond Worst-Case Analysis for Root Isolation AlgorithmsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535475(139-148)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535475
Dai LFan ZXia BZhang H(2019)Logcf: An Efficient Tool for Real Root IsolationJournal of Systems Science and Complexity10.1007/s11424-019-7361-732:6(1767-1782)Online publication date: 14-Dec-2019
https://doi.org/10.1007/s11424-019-7361-7
Johnson J(2012)In MemoriamACM Communications in Computer Algebra10.1145/2338496.233850446:1/2(52-54)Online publication date: 23-Jul-2012
https://dl.acm.org/doi/10.1145/2338496.2338504
Chen CMaza MXie Y(2012)Cache Complexity and Multicore Implementation for Univariate Real Root IsolationJournal of Physics: Conference Series10.1088/1742-6596/341/1/012026341(012026)Online publication date: 9-Feb-2012
https://doi.org/10.1088/1742-6596/341/1/012026
Emiris IPan VTsigaridas E(2010)Algebraic and numerical algorithmsAlgorithms and theory of computation handbook10.5555/1882757.1882774(17-17)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.5555/1882757.1882774
Emiris IGalligo ATsigaridas EKoepf W(2010)Random polynomials and expected complexity of bisection methods for real solvingProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1837980(235-242)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1837934.1837980
Hemmer MTsigaridas EZafeirakopoulos ZEmiris IKaravelas MMourrain BSasaki TShirayanagi KKotsireas I(2009)Experimental evaluation and cross-benchmarking of univariate real solversProceedings of the 2009 conference on Symbolic numeric computation10.1145/1577190.1577202(45-54)Online publication date: 3-Aug-2009
https://dl.acm.org/doi/10.1145/1577190.1577202
Li XMoreno Maza MSchost É(2009)Fast arithmetic for triangular setsJournal of Symbolic Computation10.1016/j.jsc.2008.04.01944:7(891-907)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.jsc.2008.04.019
Char BSaunders BYouse BMaza M(2007)LinBox and future high performance computer algebraProceedings of the 2007 international workshop on Parallel symbolic computation10.1145/1278177.1278197(102-103)Online publication date: 27-Jul-2007
https://dl.acm.org/doi/10.1145/1278177.1278197
Li XMaza MSchost ÉWang D(2007)Fast arithmetic for triangular setsProceedings of the 2007 international symposium on Symbolic and algebraic computation10.1145/1277548.1277585(269-276)Online publication date: 29-Jul-2007
https://dl.acm.org/doi/10.1145/1277548.1277585
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents