research-article

Real root isolation for tame elementary functions

Author:

Adam StrzebonskiAuthors Info & Claims

ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation

Pages 341 - 350

https://doi.org/10.1145/1576702.1576749

Published: 28 July 2009 Publication History

Get Access

Abstract

We present a real root isolation procedure for univariate elementary functions. The procedure finds the domain and the zero set of a function f in an arbitrary, possibly unbounded, interval as long as f is represented by a tame expression. An elementary expression is tame if the arguments of its trigonometric subexpressions are bounded. We discuss implementation of the procedure and give empirical results. The procedure requires the ability to determine signs of elementary functions at simple roots of other elementary functions. The currently known method to do this depends on Schanuel's conjecture [7].

References

[1]

A. G. Akritas and A. Strzebo&#324;nski. A comparative study of two real root isolation methods. Nonlinear Analysis: Modelling and Control, 10(4):297--304, 2005.

Crossref

Google Scholar

[2]

D. Gruntz. On computing limits in a symbolic manipulation system. PhD thesis, ETH, 1996.

Google Scholar

[3]

A. G. Hovanskii. On a class of systems of transcendental equations. Soviet Math. Dokl., 22:762--765, 1980.

Google Scholar

[4]

S. Lang. Introduction to transcendental numbers. Addison-Wesley, 1966.

Google Scholar

[5]

C. Li, S. Pion, and C. K. Yap. Recent progress in exact geometric computation. J. of Logic and Algebraic Programming, 64:85--111, 2005.

Crossref

Google Scholar

[6]

D. Richardson. Computing the topology of a bounded non algebraic curve in the plane. J. Symb. Comput., 14:619--643, 1992.

Digital Library

Google Scholar

[7]

D. Richardson. How to recognize zero. J. Symb. Comput., 24:627--645, 1997.

Digital Library

Google Scholar

[8]

D. Richardson. Zero tests for constants in simple scientific computation. Mathematics in Computer Science, 1:21--37, 2007.

Crossref

Google Scholar

[9]

D. Richardson. Recognising zero among implicitly defined elementary numbers. Preprint (2009), submitted to J. Symb. Comput.

Google Scholar

[10]

A. Strzebo&#324;nski. Real root isolation for exp-log functions. In D. Jeffrey, editor, Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2008, pages 303--313. ACM, 2008.

Digital Library

Google Scholar

[11]

L. van den Dries, A. Macintyre, and D. Marker. The elementary theory of restricted analytic fields with exponentiation. Ann. Math., 140:183--205, 1994.

Crossref

Google Scholar

[12]

E. Weisstein. Mathworld. http://mathworld.wolfram.com.

Google Scholar

[13]

A. J. Wilkie. Model completeness results for expansions of the ordered field of real numbers by restricted pfaffian functions and the exponential function. J. Amer. Math. Soc., 9:1051--1094, 1996.

Crossref

Google Scholar

[14]

A. J. Wilkie. A theorem of the complement and some new o-minimal structures. Selecta Math., New Series, 5(4):397--421, 1999.

Google Scholar

Cited By

View all

Chen RXia B(2024)Reduction of Transcendental Decision Problems over the RealsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669675(56-64)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669675
Chen RXia B(2023)Deciding first-order formulas involving univariate mixed trigonometric-polynomialsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597104(145-154)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597104
Cheng JWen JZhang B(2023)Certified numerical real root isolation for bivariate nonlinear systemsJournal of Symbolic Computation10.1016/j.jsc.2022.04.005114(149-171)Online publication date: Jan-2023
https://doi.org/10.1016/j.jsc.2022.04.005
Show More Cited By

Index Terms

Real root isolation for tame elementary functions
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
2. Mathematics of computing
  1. Mathematical software

Recommendations

Real root isolation for exp-log functions
ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation

We present a real root isolation procedure for univariate functions obtained by composition and rational operations from exp, log, and real constants. We discuss implementation of the procedure and give empirical results. The procedure requires the ...
Real root isolation for exp-log-arctan functions

We present a real root isolation procedure for univariate functions obtained by composition and rational operations from exp,log,arctan and real constants. The procedure was first introduced for exp-log functions in Strzebonski (2008). Here we extend ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation

July 2009

402 pages

ISBN:9781605586090

DOI:10.1145/1576702

General Chairs:
Jeremy Johnson
Drexel University, USA
,
Hyungju Park
Korea Institute for Advanced Study, Korea
,
Program Chair:
Erich Kaltofen
North Carolina State University, USA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '09

Sponsor:

ISSAC '09: International Symposium on Symbolic and Algebraic Computation

July 28 - 31, 2009

Seoul, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
194
Total Downloads

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

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen RXia B(2024)Reduction of Transcendental Decision Problems over the RealsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669675(56-64)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669675
Chen RXia B(2023)Deciding first-order formulas involving univariate mixed trigonometric-polynomialsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597104(145-154)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597104
Cheng JWen JZhang B(2023)Certified numerical real root isolation for bivariate nonlinear systemsJournal of Symbolic Computation10.1016/j.jsc.2022.04.005114(149-171)Online publication date: Jan-2023
https://doi.org/10.1016/j.jsc.2022.04.005
Huang CMaza MZhi L(2022)Explicit Bounds for Linear Forms in the Exponentials of Algebraic NumbersProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3536170(371-379)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3536170
Guan JYu N(2022)A Probabilistic Logic for Verifying Continuous-time Markov ChainsTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-030-99527-0_1(3-21)Online publication date: 30-Mar-2022
https://doi.org/10.1007/978-3-030-99527-0_1
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
Cheng JWen JDavenport JWang DKauers MBradford R(2019)Certified Numerical Real Root Isolation for Bivariate Polynomial SystemsProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326237(90-97)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326237
Chen MWang JAn JZhan BKapur DZhan N(2019)NIL: Learning Nonlinear InterpolantsAutomated Deduction – CADE 2710.1007/978-3-030-29436-6_11(178-196)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-29436-6_11
Huang CXu MLi Z(2018)A Conflict-Driven Solving Procedure for Poly-Power ConstraintsJournal of Automated Reasoning10.1007/s10817-018-09501-zOnline publication date: 5-Dec-2018
https://doi.org/10.1007/s10817-018-09501-z
Li JHuang CXu MLi ZAbramov SZima EGao X(2016)Positive Root Isolation for Poly-PowersProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930909(325-332)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930909
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.

Cited By

Index Terms

Recommendations

Real root isolation for exp-log functions

Real root isolation for exp-log-arctan functions

Univariate real root isolation in multiple extension fields