NDLI: Experimental evaluation and cross-benchmarking of univariate real solvers

Please wait, while we are loading the content...

Pseudospectra for exponential polynomial matrices

Rigorous global search using taylor models

Parametrization of ε-rational curves: extended abstract

Error free transformations of floating point numbers and its applications to constructing efficient error free numerical algorithms

Exact polynomial factorization by approximate high degree algebraic numbers

Preconditioning, randomization, solving linear systems, eigen-solving, and root-finding

Computing nearest Gcd with certification

Symbolic-numeric problems in the automatic analysis and verification of cyber-physical systems

Extracting numerical factors of multivariate polynomials from taylor expansions

De-Sinc numerical methods

Experimental evaluation and cross-benchmarking of univariate real solvers

An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination

A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functions

Curve/surface intersection problem by means of matrix representations

Rigorous integration of flows and ODEs using taylor models

Continued fraction expansion of real roots of polynomial systems

Application of filter diagonalization method to numerical solution of algebraic equations

Nearly optimal symbolic-numerical algorithms for structured integer matrices and polynomials

Continuations and monodromy on random riemann surfaces

Finding exact minimal polynomial by approximations

Optimization and NP_R-completeness of certain fewnomials

A method for finding zeros of polynomial equations using a contour integral based eigensolver

Computing multivariate approximate GCD based on Barnett's theorem

Convergence and many-valuedness of hensel seriesnear the expansion point

Approximate factorization of polynomials over Z

Computing clustered close-roots of univariate polynomials

Finding positively invariant sets of a class of nonlinear loops via curve fitting

Reducing exact computations to obtain exact results based on stabilization techniques

Experimental evaluation and cross-benchmarking of univariate real solvers

Content Provider	ACM Digital Library
Author	Tsigaridas, Elias P. Mourrain, Bernard Zafeirakopoulos, Zafeirakis Hemmer, Michael Emiris, Ioannis Z. Karavelas, Menelaos I.
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.
Starting Page	45
Ending Page	54
Page Count	10
File Format	PDF
ISBN	9781605586649
DOI	10.1145/1577190.1577202
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-08-03
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Real root isolation Benchmarks Univariate polynomial
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Experimental evaluation and cross-benchmarking of univariate real solvers (2009)

Experimental evaluation and cross-benchmarking of univariate real solvers (2008).

Univariate real root isolation in multiple extension fields

Univariate real root isolation in an extension field

Univariate polynomial real root isolation: Continued fractions revisited (2006)

A root isolation algorithm for sparse univariate polynomials

Efficient Isolation of a Polynomial Real Roots

Univariate Real Root Isolation in Multiple Extension Fields (2012)

Computations with one and two real algebraic numbers

Experimental evaluation and cross-benchmarking of univariate real solvers

Similar Documents

Experimental evaluation and cross-benchmarking of univariate real solvers (2009)

Experimental evaluation and cross-benchmarking of univariate real solvers (2008).

Univariate real root isolation in multiple extension fields

Univariate real root isolation in an extension field

Univariate polynomial real root isolation: Continued fractions revisited (2006)

A root isolation algorithm for sparse univariate polynomials

Efficient Isolation of a Polynomial Real Roots

Univariate Real Root Isolation in Multiple Extension Fields (2012)

Computations with one and two real algebraic numbers

Experimental evaluation and cross-benchmarking of univariate real solvers