Better simplification of elementary functions through power series

ABSTRACT

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 consistent.In [14] an algorithm was presented for zero-testing functions defined by ordinary differential equations, in terms of their power series.The purpose of the current paper is to investigate merging the two techniques. In particular, we will show an explicit reduction to the constant problem [16].

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: Dennis S. Arnon, A cluster-based cylindrical algebraic decomposition algorithm, Journal of Symbolic Computation, v.5 n.1-2, p.189-212, February/April 1988 [doi>10.1016/S0747-7171(88)80012-9]
• 3: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition II: an adjacency algorithm for the plane, SIAM Journal on Computing, v.13 n.4, p.878-889, Nov. 1984 [doi>10.1137/0213055]
• 4: Beaumont, J., Bradford, R., and Davenport, J. Towards Better Simplification of Elementary Functions. Pre-print, University of Bath, England. (2002).
• 5: Russell Bradford , James H. Davenport, Towards better simplification of elementary functions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.16-22, July 07-10, 2002, Lille, France [doi>10.1145/780506.780509]
• 6: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 7: Robert M. Corless , David J. Jeffrey , Stephen M. Watt , James H. Davenport, “According to Abramowitz and Stegun” or arccoth needn't be uncouth, ACM SIGSAM Bulletin, v.34 n.2, p.58-65, June, 2000 [doi>10.1145/362001.362023]
• 8: Corless, R., Gonnet, G., Jeffrey, D., Hare, D., and Knuth, D. On the Lambert W Function. In Advances in Computational Mathematics 5, (1996), 329--359.
• 9: James H. Davenport, Table errata, Mathematics of Computation, v.71 n.240, p.1801-1801, October 2002
• 10: James H. Davenport , Joos Heintz, Real quantifier elimination is doubly exponential, Journal of Symbolic Computation, v.5 n.1-2, p.29-35, February/April 1988 [doi>10.1016/S0747-7171(88)80004-X]
• 11: Gabrielov, A., and Vorobjov, N. Complexity of cylindrical decompositions of sub-Pfaffian sets. J. Pure Appl. Algebra 164 (2001), 179--197.
• 12: Henrici, P. Applied and Computational Complex Analysis. Vol.1, Wiley and Sons, (1974).
• 13: Hölder, O. Über die Eigenschaft der Gamma Funktion keineralgebraischen Differentialgleichungen zu genügen. Math. Ann. 28 (1887), 1--13.
• 14: Joris van der Hoeven, A new zero-test for formal power series, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.117-122, July 07-10, 2002, Lille, France [doi>10.1145/780506.780521]
• 15: Kahan, W. Branch Cuts for Complex Elementary Functions. The State of Art in Numerical Analysis (1987), 165--211.
• 16: Richardson, D. Some Unsolvable Problems Involving Elementary Functions of a Real Variable. Journal of Symbolic Logic 33 (1968), 514--520.
• 17: Daniel Richardson, How to recognize zero, Journal of Symbolic Computation, v.24 n.6, p.627-645, Dec. 1997 [doi>10.1006/jsco.1997.0157]
• 18: Smyth, C. An explicit formula for the Mahler measure of a family of 3-variable polynomials. To appear in J. Théor. Nombres Bordeaux (2002).
• 19: Trudy Weibel , Gaston H. Gonnet, An Assume Facility for CAS, with a Sample Implementation for Maple, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.95-103, April 13-15, 1992

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms, Theory

Keywords:
simplification power series