×

Testing elementary function identities using CAD. (English) Zbl 1142.68618

Summary: One of the problems with manipulating function identities in computer algebra systems is that they often involve functions which are multivalued, whilst most users tend to work with single-valued functions. The problem is that many well-known identities may no longer be true everywhere in the complex plane when working with their single-valued counterparts. Conversely, we cannot ignore them, since in particular contexts they may be valid. We investigate the practicality of a method to verify such identities by means of an experiment; this is based on a set of test examples which one might realistically meet in practice. Essentially, the method works as follows. We decompose the complex plane via means of cylindrical algebraic decomposition into regions with respect to the branch cuts of the functions. We then test the identity numerically at a sample point in each region. The latter step is facilitated by the notion of the adherence of a branch cut, which was previously introduced by the authors. In addition to presenting the results of the experiment, we explain how adherence relates to the proposal of signed zeroes by W. Kahan, and develop this idea further in order to allow us to cover previously untreatable cases. Finally, we discuss other ways to improve upon our general methodology as well as topics for future research.

MSC:

68W30 Symbolic computation and algebraic computation
13P99 Computational aspects and applications of commutative rings

Software:

QEPCAD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramowitz, M., Stegun, I.: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. US Government Printing Office (1964; 10th printing, 1972) · Zbl 0171.38503
[2] Arnon D.S. (1988). A cluster-based CAD algorithm. J. Symb. Comput. 5(1/2): 189–212 · Zbl 0648.68056 · doi:10.1016/S0747-7171(88)80012-9
[3] Bradford, R., Davenport, J.H.: Towards better simplification of elementary functions. In: Mora, T. (ed.) Proceedings of ISSAC, Lille, 7–10 July, pp. 15–22. ACM, New York (2002) · Zbl 1072.68651
[4] Beaumont, J.C., Bradford, R., Davenport, J.H.: Better simplification of elementary functions through power series. In: Sendra, J.R. (ed.) Proceedings of ISSAC, Philadelphia, 3–6 August, pp. 30–36. ACM, New York (2003) · Zbl 1072.68646
[5] Beaumont, J.C., Bradford, R., Davenport, J.H., Phisanbut, N.: A Poly-algorithmic approach to simplifying elementary functions. In: Guttierez, J. (ed.) Proceedings of ISSAC, Santander, 4–7 July, pp. 30–36. ACM, New York (2004) · Zbl 1134.68594
[6] Beaumont, J. C., Bradford, R., Phisanbut, N.: Practical simplification of elementary functions using CAD. In: Dolzmann, A., Seidl, A., Sturm, T. (eds.) Proceedings of Algorithmic Algebra and Logic, Passau, 3–6 April. Books on Demand GmbH, Norderstedt, Germany (2005)
[7] Beaumont, J.C., Bradford, R., Davenport, J.H., Phisanbut, N.: Adherence is better than adjacency: computing the riemann index using CAD. In: Kauers Editor, M. (ed.) Proceedings of ISSAC, Beijing, 24–27 July, pp. 37–45. ACM, New York (2005) · Zbl 1360.14140
[8] Bradford R., Corless R., Davenport J., Jeffrey D. and Watt S. (2002). Reasoning about the elementary functions of complex analysis. Ann. Math. Artif. Intel. 36: 303–318 · Zbl 1007.30001 · doi:10.1023/A:1016007415899
[9] Brown, C.: Companion to the Tutorial Cylindrical Algebraic Decomposition, Presented at ISSAC 2004. Available at: www.cs.usna.edu/cbrown/research/ISSAC04/Tutorial.html
[10] Brown, C., McCallum, S.: On Using Bi-equational constraints in CAD construction. In: Kauers, M. (ed.) Proceedings of ISSAC, Beijing, pp. 76–84. ACM, New York (2005) · Zbl 1360.68925
[11] Collins, G.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Proceedings of 2nd GI Conference Automata Theory & Formal Languages, vol. 33 of Springer Lecture Notes in Computer Science (1975) · Zbl 0318.02051
[12] Collins G. and Hong H. (1991). Partial CAD for quantifier elimination. J. Symb. Comput. 12(3): 299–328 · Zbl 0754.68063 · doi:10.1016/S0747-7171(08)80152-6
[13] Collins G. and McCallum S. (2002). Local box adjacency algorithms for CAD. J. Symb. Comput. 33(3): 321–342 · Zbl 1014.11002 · doi:10.1006/jsco.2001.0518
[14] Corless R., Davenport J., Jeffrey D. and Watt S. (2002). According to Abramowitz and Stegun. SIGSAM Bull. 34(2): 58–65 · doi:10.1145/362001.362023
[15] Corless R. and Jeffrey D. (1996). The unwinding number. SIGSAM Bull. 30(2 issue 116): 28–35 · doi:10.1145/235699.235705
[16] Davenport J. and Heintz J. (1988). Real quantifier elimination is doubly exponential. J. Symb. Comput. 5: 29–35 · Zbl 0663.03015 · doi:10.1016/S0747-7171(88)80004-X
[17] Dolzmann, A, Seidl, A, Sturm, T.: Efficient projection orders for CAD. In: Guttierez, J. (ed.) Proceedings of ISSAC, Santander, 4–7 July, pp. 111–118. ACM, New York (2004) · Zbl 1134.68575
[18] Fateman, R.J., Dingle, A.: Branch cuts in computer algebra. In: Giesbrecht, M. (ed.) Proceedings of ISSAC, Oxford, 20–22 July, pp. 250–257. ACM Press, New York (1994) · Zbl 0928.68146
[19] Grigoryev D.Yu. and Vorobjov N. (1992). Counting connected components of a semi-algebraic set in subexponential time. Comput. Complex. 2: 133–184 · Zbl 0900.68253 · doi:10.1007/BF01202001
[20] Jeffrey D.J. and Norman A.C. (2004). Not seeing the roots for the branches: multivalued functions in computer algebra. SIGSAM Bull. 38(3 issue 149): 57–66 · Zbl 1341.68312 · doi:10.1145/1040034.1040036
[21] Kahan W. (1987). Branch cuts for complex elementary functions. In: Iserles, A. and Powell, M. (eds) The State of Art in Numerical Analysis: Proc. Joint IMA/SIAM, U.N., pp 165–211. Clarendon Press, New York · Zbl 0615.65014
[22] Patton C.M. (1996). A representation of branch-cut information. SIGSAM Bull. 116: 21–24 · doi:10.1145/235699.235703
[23] Hong, H. et al.: Quantifier Elimination by Partial Cylindrical Algebraic Decomposition. Available at: http://www.cs.usna.edu/epcad/B/QEPCAD.html
[24] Richardson D. (1968). Some unsolvable problems involving elementary functions of a real variable. J. Symb. Logic 33: 514–520 · Zbl 0175.27404 · doi:10.2307/2271358
[25] Rich A. and Jeffrey D. (1996). Function evaluation on branch cuts. SIGSAM Bull. 116: 25–27 · doi:10.1145/235699.235704
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.