Article

Towards better simplification of elementary functions

Authors:

Russell Bradford,

James H. DavenportAuthors Info & Claims

ISSAC '02: Proceedings of the 2002 international symposium on Symbolic and algebraic computation

Pages 16 - 22

https://doi.org/10.1145/780506.780509

Published: 10 July 2002 Publication History

Abstract

We present an algorithm for simplifying a large class of elementary functions in the presence of branch cuts. This algorithm works by:(a) verifying that the proposed simplification is correct as a simplification of multi-valued functions;(b) decomposing C (or Cⁿ in the case of multivariate simplifications) according to the branch cuts of the relevant functions;(c) checking that the proposed identity is valid on each component of that decomposition.This process can be interfaced to an assume facility, and, if required, can verify that simplifications are valid "almost everywhere".

References

[1]

Abramowitz,M. & Stegun,I., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. US Government Printing Office, 1964. 10th Printing December 1972.]]

Digital Library

[2]

Arnon,D. S., A Cluster-Based Cylindrical Algebraic Decomposition Algorithm. J. Symbolic Comp.5 (1988) pp. 189-211. Also Algorithms in Real Algebraic Geometry (ed. D. S. Arnon & B. Buchberger), Academic Press, London, 1988.]]

Digital Library

[3]

Arnon,D. S. & McCallum,S., Cylindrical Algebraic Decomposition II: An Adjacency Algorithm for the Plane. SIAM J. Comp.13 (1984) pp. 878-889.]]

Digital Library

[4]

Borodin,A., Fagin,R., Hopcroft,J. E. & Tompa,M., Decreasing the Nesting Depth of an Expression Involving Square Roots. J. Symbolic Comp.1 (1985) pp. 169-188.]]

Digital Library

[5]

Bradford,R. J., Corless,R. M., Davenport,J. H., Jeffrey,D. J., & Watt,S. M., Reasoning about the Elementary Functions of Complex Analysis. To appear in Annals of Mathematics and Artificial Intelligence.]]

Digital Library

[6]

Collins,G. E., Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. Proc. 2nd. GI Conference Automata Theory & Formal Languages (Springer Lecture Notes in Computer Science 33), Springer-Verlag, 1975, pp. 134-183. MR 55 (1978) #771.]]

Digital Library

[7]

Corless,R. M., Davenport,J. H., Jeffrey,D. J., Litt,G. & Watt,S. M., Reasoning about, the Elementary Functions of Complex Analysis. Artificial Intelligence and Symbolic Computation (ed. John A. Campbell & Eugenio Roanes-Lozano), Springer Lecture Notes in Artificial Intelligence Vol. 1930, Springer-Verlag 2001, pp. 115-126. http://www.apmaths.uwo.ca/~djeffrey/offprints.html. http://link.springer.de/link/service/series/0558/bibs/1930/19300115.htm]]

Digital Library

[8]

Corless,R. M., Davenport,J. H., Jeffrey, D. J. & Watt,S. M., "According to Abramowitz and Stegun". SIGSAM Bulletin34 (2000) 2, pp. 58-65.]]

Digital Library

[9]

Corless,R. M. & Jeffrey,D. J., The Unwinding Number. SIGSAM Bulletin30 (1996) 2, issue 116, pp. 28-35.]]

Digital Library

[10]

Davenport,J. H. & Heintz,J., Real Quantifier Elimination is Doubly Exponential. J. Symbolic Comp.5 (1988) pp. 29-35. Also Algorithms in Real Algebraic Geometry (ed. D. S. Arnon and B. Buchberger), Academic Press, London, 1988. Zbl. 663.03015. MR 89g:03009.]]

Digital Library

[11]

Gabrielov,A. & Vorobjov,N., Complexity of cylindrical decompositions of sub-Pfaffian sets. J. Pure Appl. Algebra164 (2001) pp. 179-197.]]

[12]

Ménissier-Morain, V., Arithmétique exacte, conception, algorithmique et performances d'une implémentation informatique en précision arbitraire. Thèse, Université Paris 7, Dec. 1994.]]

[13]

Richardson,D., Some Unsolvable Problems Involving Elementary Functions of a Real Variable. Journal of Symbolic Logic33(1968), pp. 514-520.]]

[14]

Risch,R. H., Algebraic Properties of the Elementary Functions of Analysis. Amer. J. Math.101 (1979) pp. 743-759. MR 81b:12029.]]

[15]

Weibel,T. & Gonnet,G. H., An Assume Facility for CAS with a Sample Implementation for Maple. Proc. DISCO '92 (Springer Lecture Notes in Computer Science 721, ed. J. P. Fitch), Springer-Verlag, 1993, pp. 95-103.]]

Digital Library

Cited By

Orlando G(2021)Kaldor–Kalecki New Model on Business CyclesNonlinearities in Economics10.1007/978-3-030-70982-2_16(247-268)Online publication date: 16-Feb-2021
https://doi.org/10.1007/978-3-030-70982-2_16
Orlando G(2018)Chaotic Business Cycles within a Kaldor-Kalecki FrameworkNonlinear Dynamical Systems with Self-Excited and Hidden Attractors10.1007/978-3-319-71243-7_6(133-161)Online publication date: 27-Feb-2018
https://doi.org/10.1007/978-3-319-71243-7_6
Orlando G(2016)A discrete mathematical model for chaotic dynamics in economicsMathematics and Computers in Simulation10.1016/j.matcom.2016.01.001125:C(83-98)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.matcom.2016.01.001
Show More Cited By

Recommendations

Branch cuts in maple 17

Accurate and comprehensible knowledge about the position of branch cuts is essential for correctly working with multi-valued functions, such as the square root and logarithm. We discuss the new tools in Maple 17 for calculating and visualising the ...
Better simplification of elementary functions through power series
ISSAC '03: Proceedings of the 2003 international symposium on Symbolic and algebraic computation

In [5], we introduced an algorithm for deciding whether a proposed simplification of elementary functions was correct in the presence of branch cuts. This algorithm used multivalued function simplification followed by verification that the branches were ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '02: Proceedings of the 2002 international symposium on Symbolic and algebraic computation

July 2002

296 pages

ISBN:1581134843

DOI:10.1145/780506

Conference Chair:
Marc Giusti
CNRS-Ecole Polytechnique, France

Copyright © 2002 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

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 July 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC02

Sponsor:

SIGSAM

ISSAC02: International Symposium on Symbolic and Algebraic Computation

July 7 - 10, 2002

Lille, France

Acceptance Rates

ISSAC '02 Paper Acceptance Rate 35 of 86 submissions, 41%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
135
Total Downloads

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

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Orlando G(2021)Kaldor–Kalecki New Model on Business CyclesNonlinearities in Economics10.1007/978-3-030-70982-2_16(247-268)Online publication date: 16-Feb-2021
https://doi.org/10.1007/978-3-030-70982-2_16
Orlando G(2018)Chaotic Business Cycles within a Kaldor-Kalecki FrameworkNonlinear Dynamical Systems with Self-Excited and Hidden Attractors10.1007/978-3-319-71243-7_6(133-161)Online publication date: 27-Feb-2018
https://doi.org/10.1007/978-3-319-71243-7_6
Orlando G(2016)A discrete mathematical model for chaotic dynamics in economicsMathematics and Computers in Simulation10.1016/j.matcom.2016.01.001125:C(83-98)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.matcom.2016.01.001
Bradford RDavenport JEngland MMcCallum SWilson D(2016)Truth table invariant cylindrical algebraic decompositionJournal of Symbolic Computation10.1016/j.jsc.2015.11.00276:C(1-35)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.jsc.2015.11.002
England MCheb-Terrab EBradford RDavenport JWilson D(2014)Branch cuts in maple 17ACM Communications in Computer Algebra10.1145/2644288.264429348:1/2(24-27)Online publication date: 10-Jul-2014
https://dl.acm.org/doi/10.1145/2644288.2644293
Wilson DBradford RDavenport JEngland M(2014)Cylindrical Algebraic Sub-DecompositionsMathematics in Computer Science10.1007/s11786-014-0191-z8:2(263-288)Online publication date: 13-Jun-2014
https://doi.org/10.1007/s11786-014-0191-z
England MBradford RDavenport JWilson D(2014)Choosing a Variable Ordering for Truth-Table Invariant Cylindrical Algebraic Decomposition by Incremental Triangular DecompositionMathematical Software – ICMS 201410.1007/978-3-662-44199-2_68(450-457)Online publication date: 2014
https://doi.org/10.1007/978-3-662-44199-2_68
Bradford RChen CDavenport JEngland MMoreno Maza MWilson D(2014)Truth Table Invariant Cylindrical Algebraic Decomposition by Regular ChainsComputer Algebra in Scientific Computing10.1007/978-3-319-10515-4_4(44-58)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10515-4_4
Wilson DDavenport JEngland MBradford R(2013)A "Piano Movers" Problem ReformulatedProceedings of the 2013 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing10.1109/SYNASC.2013.14(53-60)Online publication date: 23-Sep-2013
https://dl.acm.org/doi/10.1109/SYNASC.2013.14
England MBradford RDavenport JWilson D(2013)Understanding branch cuts of expressionsProceedings of the 2013 international conference on Intelligent Computer Mathematics10.1007/978-3-642-39320-4_9(136-151)Online publication date: 8-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39320-4_9
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