A poly-algorithmic approach to simplifying elementary functions

ABSTRACT

Simplification has been long recognised to be a fundamental problem within computer algebra [17]. However, even for the class of elementary functions, it has not been resolved in a satisfactory way.Algorithms were presented in [4, 2] to solve this problem, and it was seen that both methods had their own strengths and weaknesses. Also, not all functions could be handled by either of the methods alone. The current paper continues this line of development by combining the two methods, and reporting on progress made with the various sub-algorithms involved.

REFERENCES

• 1: Beaumont, J., Bradford, R., and Davenport, J. Towards Better Simplification of Elementary Functions. Pre-print, University of Bath, England. (2002). http://www.cs.bath.ac.uk/cspnp/simplification/mvfunc.html
• 2: James Beaumont , Russell Bradford , James H. Davenport, Better simplification of elementary functions through power series, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.30-36, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860867]
• 3: Russell Bradford , Robert M. Corless , James H. Davenport , David J. Jeffrey , Stephen M. Watt, Reasoning about the Elementary Functions of Complex Analysis, Annals of Mathematics and Artificial Intelligence, v.36 n.3, p.303-318, November 2002 [doi>10.1023/A:1016007415899]
• 4: 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]
• 5: Christopher W. Brown, Simple CAD construction and its applications, Journal of Symbolic Computation, v.31 n.5, p.521-547, May 2001 [doi>10.1006/jsco.2000.0394]
• 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: George E. Collins , Hoon Hong, Partial cylindrical algebraic decomposition for quantifier elimination, Journal of Symbolic Computation, v.12 n.3, p.299-328, Sept. 1991 [doi>10.1016/S0747-7171(08)80152-6]
• 8: 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]
• 9: Robert M. Corless , David J. Jeffrey, The unwinding number, ACM SIGSAM Bulletin, v.30 n.2, p.28-35, June 1996 [doi>10.1145/235699.235705]
• 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: Adam Dingle , Richard J. Fateman, Branch cuts in computer algebra, Proceedings of the international symposium on Symbolic and algebraic computation, p.250-257, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190424]
• 12: D. Yu. Grigor'ev , N. N. Vorobjov, Jr., Counting connected components of a semialgebraic set in subexponential time, Computational Complexity, v.2 n.2, p.133-186, 1992 [doi>10.1007/BF01202001]
• 13: Gabrielov, A., and Vorobjov, N. Complexity of cylindrical decompositions of sub-Pfaffian sets. J. Pure Appl. Algebra 164 (2001), 179--197.
• 14: Henrici, P. Applied and Computational Complex Analysis. Vol.1, Wiley and Sons, (1974).
• 15: Kahan, W. Branch Cuts for Complex Elementary Functions. The State of Art in Numerical Analysis (1987), 165--211.
• 16: Mansfield, E. L. Differential Gröbner Bases. Ph.D. Thesis, University of Sydney, 1992.Mansfield, E. L. Differential Gröbner Bases. Ph.D. Thesis, University of Sydney, 1992.
• 17: Moses, J. Algebraic Simplification, a Guide for the Perplexed. In Advances in Computational Mathematics 14, no.8 (1971).
• 18: Charles M. Patton, A representation of branch-cut information, ACM SIGSAM Bulletin, v.30 n.2, p.21-24, June 1996 [doi>10.1145/235699.235703]
• 19: H. Hong et al. Quantifier Elimination by Partial Cylindrical Algebraic Decomposition.
• 20: Richardson, D. Some Unsolvable Problems Involving Elementary Functions of a Real Variable. Journal of Symbolic Logic 33 (1968), pp. 514--520.
• 21: 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]
• 22: 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]

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
branch cuts, simplification