research-article

Experimental evaluation and cross-benchmarking of univariate real solvers

Authors:

Michael Hemmer,

Elias P. Tsigaridas,

Zafeirakis Zafeirakopoulos,

Ioannis Z. Emiris,

Menelaos I. Karavelas,

Bernard MourrainAuthors Info & Claims

SNC '09: Proceedings of the 2009 conference on Symbolic numeric computation

Pages 45 - 54

https://doi.org/10.1145/1577190.1577202

Published: 03 August 2009 Publication History

Abstract

Real solving of univariate polynomials is a fundamental problem with several important applications. This paper is focused on the comparison of black-box implementations of state-of-the-art algorithms for isolating real roots of univariate polynomials over the integers. We have tested 9 different implementations based on symbolic-numeric methods, Sturm sequences, Continued Fractions and Descartes' rule of sign. The methods under consideration were developed at the GALAAD group at INRIA,the VEGAS group at LORIA and the MPI Saarbrücken. We compared their sensitivity with respect to various aspects such as degree, bitsize or root separation of the input polynomials. Our datasets consist of 5,000 polynomials from many different settings, which have maximum coefficient bitsize up to bits 8,000, and the total running time of the experiments was about 50 hours. Thereby, all implementations of the theoretically exact methods always provided correct results throughout this extensive study. For each scenario we identify the currently most adequate method, and we point to weaknesses in each approach, which should lead to further improvements. Our results indicate that there is no "best method" overall, but one can say that for most instances the solvers based on Continued Fractions are among the best methods. To the best of our knowledge, this is the largest number of tests for univariate real solving up to date.

References

[1]

A. Akritas, A. Strzebonski, and P. Vigklas. Improving the performance of the continued fractions method using new bounds of positive roots. Nonlinear Analysis, 13(3):265--279, 2008.

[2]

M. H. Austern. Generic Programming and the STL. Addison-Wesley, 1998.

Digital Library

[3]

E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, L. Kettner, K. Mehlhorn, J. Reichel, S. Schmitt, E. Sch&#246;mer, and N. Wolpert. Exacus: Efficient and exact algorithms for curves and surfaces. In 13th Annual European Symp. on Algorithms (ESA), volume 3669 of LNCS, pages 155--166, Palma de Mallorca, Spain, 2005. Springer.

Digital Library

[4]

E. Berberich, M. Hemmer, M. I. Karavelas, and M. Teillaud. Revision of the interface specification of algebraic kernel. Technical Report ACS-TR-243301-01, INRIA, MPI and NUA, 2007.

[5]

D. Bini and G. Fiorentino. Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numerical Algorithms, pages 127--173, 2000.

[6]

G. Collins, J. Johnson, and W. Krandick. Interval arithmetic in cylindrical algebraic decomposition. J. of Symbolic Computation, 34:143--155, 2002.

Digital Library

[7]

G. E. Collins and A. G. Akritas. Polynomial real root isolation using descarte's rule of signs. In Proc. 3rd ACM Symp. on Symbolic and Algebraic Comp., pages 272--275, NY, USA, 1976.

Digital Library

[8]

J. H. Davenport. Cylindrical algebraic decomposition. Technical Report 88--10, School of Mathematical Sciences, University of Bath, England, 1988.

[9]

Z. Du, V. Sharma, and C. K. Yap. Amortized bound for root isolation via Sturm sequences. In D. Wang and L. Zhi, editors, Int. Workshop on Symbolic Numeric Computing, pages 113--129, School of Science, Beihang University, Beijing, China, 2005. Birkhauser.

[10]

A. Eigenwillig. Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs. PhD thesis, Universit&#228;t des Saarlandes, Saarbr&#228;cken, 2008.

[11]

A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt, and N. Wolpert. A descartes algorithm for polynomials with bit-stream coefficients. In Proc. 8th Int. Workshop on Computer Algebra in Scient. Comput. (CASC), volume 3718 of LNCS, pages 138--149, Kalamata, Greece, 2005. Springer.

Digital Library

[12]

A. Eigenwillig, V. Sharma, and C. K. Yap. Almost tight recursion tree bounds for the Descartes method. In Proc. Annual ACM ISSAC, pages 71--78, New York, USA, 2006.

Digital Library

[13]

I. Emiris, E. Tsigaridas, and G. Tzoumas. Predicates for the exact Voronoi diagram of ellipses under the Euclidean metric. Intern. J. Comp. Geometry & Appl., 18(6):567--597, 2008. Special Issue on SoCG'06.

[14]

I. Emiris, E. Tsigaridas, and G. Tzoumas. Voronoi diagram of ellipses in CGAL. In Proc. Europ. Works. Comp. Geom., pages 87--90, Nancy, France, 2008.

[15]

I. Emiris and G. Tzoumas. Exact and efficient decision of the InCircle predicate for parametric ellipses and smooth convex objects. Computer-Aided Design (Elsevier), 40:691--700, 2008. Special issue on SPM'07.

Digital Library

[16]

I. Z. Emiris, B. Mourrain, and E. P. Tsigaridas. Real Algebraic Numbers: Complexity Analysis and Experimentation. In Reliable Implementations of Real Number Algorithms: Theory and Practice, volume 5045 of LNCS, pages 57--82. Springer Verlag, 2008.

Digital Library

[17]

I. Z. Emiris and E. P. Tsigaridas. Real algebraic numbers and polynomial systems of small degree. Theoretical Computer Science, 409(2):186--199, 2008.

Digital Library

[18]

M. Hemmer and D. H&#252;lse. Generic implementation of a modular gcd over algebraic extension fields. In 25th European Workshop on Computational Geometry, pages 321--324, Brussels, Belgium, 2009. Universit&#233; Libre de Bruxelles.

[19]

M. Hemmer and S. Limbach. Benchmakrs on a generic univariate algebraic kernel. Technical Report ACS-TR-243306-03, Algorithms for Complex Shapes with certified topology and numerics, Max Planck Institut f&#252;r Informatik, Saarbr&#252;cken, Germany, 2007.

[20]

J. R. Johnson, W. Krandick, K. Lynch, D. Richardson, and A. Ruslanov. High-performance implementations of the Descartes method. In Proc. Annual ACM ISSAC, pages 154--161, NY, 2006.

Digital Library

[21]

M. I. Karavelas. Preliminary cross-benchmarks of the MPI and NUA univariate algebraic kernels. Technical Report ACS-TR-243306-05, National University of Athens, 2008.

[22]

W. Krandick. Isolierung reeller nullstellen von polynomen. In J. Herzberger, editor, Wissenschaftliches Rechnen, pages 105--154. Akademie-Verlag, Berlin, 1995.

[23]

J. M. Lane and R. F. Riesenfeld. Bounds on a polynomial. BIT, 21:112--117, 1981.

[24]

S. Lazard, L. Pe&#241;aranda, and E. Tsigaridas. Univariate algebraic kernel and application to arrangements. In Symp. of Experimental Algorithms (SEA), 2009. (to ppear).

Digital Library

[25]

M. Mignotte. Mathematics for computer algebra. Springer-Verlag, New York, 1991.

Digital Library

[26]

B. Mourrain, P. Pavone, P. Tr&#233;buchet, E. P. Tsigaridas, and J. Wintz. synaps, a library for dedicated applications in symbolic numeric computations. In M. Stillman, N. Takayama, and J. Verschelde, editors, IMA Vol. in Math. and its Applications, pages 81--110. Springer, 2007.

[27]

B. Mourrain, M. Vrahatis, and J. Yakoubsohn. On the complexity of isolating real roots and computing with certainty the topological degree. J. Complexity, 18(2), 2002.

Digital Library

[28]

V. Pan. Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding. J. Symbolic Computation, 33(5):701--733, 2002.

Digital Library

[29]

F. Rouillier and P. Zimmermann. Efficient isolation of polynomial real roots. J. of Computational and Applied Mathematics, 162(1):33--50, 2003.

Digital Library

[30]

V. Sharma. Complexity of real root isolation using continued fractions. Theor. Comput. Sci., 409(2):292--310, 2008.

Digital Library

[31]

E. P. Tsigaridas. Algebraic algorithms and applications to geometry. PhD thesis, National Kapodistrian University of Athens, 2006.

[32]

E. P. Tsigaridas and I. Z. Emiris. On the complexity of real root isolation using continued fractions. Theor. Comput. Sci., 392(1-3):158--173, 2008.

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
Tonelli-Cueto JTsigaridas E(2022)Condition numbers for the cube. I: Univariate polynomials and hypersurfacesJournal of Symbolic Computation10.1016/j.jsc.2022.08.013Online publication date: Aug-2022
https://doi.org/10.1016/j.jsc.2022.08.013
Wang DXu J(2021)A symbolic-numerical algorithm for isolating real roots of certain radical expressionsJournal of Computational and Applied Mathematics10.1016/j.cam.2021.113424391:COnline publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1016/j.cam.2021.113424
Show More Cited By

Index Terms

Experimental evaluation and cross-benchmarking of univariate real solvers

Recommendations

Univariate real root isolation in multiple extension fields
ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation

We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial in B_α ∈ L[y], where L = Q(α₁,..., α_ℓ) is an algebraic extension of the rational numbers. Our bounds are single ...
A root isolation algorithm for sparse univariate polynomials
ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation

We consider a univariate polynomial f with real coefficients having a high degree N but a rather small number d + 1 of monomials, with d ≪ N. Such a sparse polynomial has a number of real root smaller or equal to d. Our target is to find for each real ...
Univariate real root isolation in an extension field
ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computation

We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial in B_α ∈ L[y], where L=Qα is a simple algebraic extension of the rational numbers. We revisit two approaches for the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SNC '09: Proceedings of the 2009 conference on Symbolic numeric computation

August 2009

210 pages

ISBN:9781605586649

DOI:10.1145/1577190

Editors:
Hiroshi Kai
Ehime University, Japan
,
Hiroshi Sekigawa
NTT Communication Science Laboratories, Japan
,
General Chairs:
Tateaki Sasaki
University of Tsukuba, Japan
,
Kiyoshi Shirayanagi
Tokai University, Japan
,
Program Chair:
Ilias Kotsireas
Wilfrid Laurier University, Canada

Copyright © 2009 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: 03 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SNC '09

Sponsor:

SNC '09: Symbolic Numeric Computation

August 3 - 5, 2009

Kyoto, Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
160
Total Downloads

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

Reflects downloads up to 01 Mar 2025

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
Tonelli-Cueto JTsigaridas E(2022)Condition numbers for the cube. I: Univariate polynomials and hypersurfacesJournal of Symbolic Computation10.1016/j.jsc.2022.08.013Online publication date: Aug-2022
https://doi.org/10.1016/j.jsc.2022.08.013
Wang DXu J(2021)A symbolic-numerical algorithm for isolating real roots of certain radical expressionsJournal of Computational and Applied Mathematics10.1016/j.cam.2021.113424391:COnline publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1016/j.cam.2021.113424
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
Yang ZLi QLu ZMa YGong ZLiu W(2017)Dual Structure Constrained Multimodal Feature Coding for Social Event Detection from Flickr DataACM Transactions on Internet Technology10.1145/301546317:2(1-20)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.1145/3015463
Alsaedi NBurnap PRana O(2017)Can We Predict a Riot? Disruptive Event Detection Using TwitterACM Transactions on Internet Technology10.1145/299618317:2(1-26)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.1145/2996183
Tsigaridas E(2016)SLVACM Communications in Computer Algebra10.1145/3015306.301531750:3(117-120)Online publication date: 4-Nov-2016
https://dl.acm.org/doi/10.1145/3015306.3015317
Harks TFalkenhausen P(2016)Robust Quantitative Comparative Statics for a Multimarket ParadoxACM Transactions on Economics and Computation10.1145/29565805:1(1-22)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2956580
Ali S(2016)A brief introduction to decolonial computingXRDS: Crossroads, The ACM Magazine for Students10.1145/293088622:4(16-21)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2930886
Bidwell N(2016)Decolonising HCI and interaction design discourse: some considerations in planning AfriCHIXRDS: Crossroads, The ACM Magazine for Students10.1145/293088422:4(22-27)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2930884
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.

Figures

Tables

Media

View Table of Conten