A new zero-test for formal power series

ABSTRACT

In this paper, we present a new zero-test for expressions which are constructed from formal power solutions to algebraic differential equations using the ring operations and differentiation. We also provide a survey of all existing methods that we know of and a detailed comparison of these methods with our approach.

REFERENCES

• 1: AX, J. On Schanuel's conjecture. Ann. of Math. 93 (1971), 252-268.
• 2: BOULIER, F. Étude et implantation de quelques algorithmes en algèbre différentielle. PhD thesis, University of Lille I, 1994.
• 3: R. P. Brent , H. T. Kung, Fast Algorithms for Manipulating Formal Power Series, Journal of the ACM (JACM), v.25 n.4, p.581-595, Oct. 1978 [doi>10.1145/322092.322099]
• 4: DENEF, J., AND LIPSHITZ, L. Power series solutions of algebraic differential equations. Math. Ann. 267 (1984), 213-238.
• 5: DENEF, J., AND LIPSHITZ, L. Decision problems for differential equations. The Journ. of Symb. Logic 54, 3 (1989), 941-950.
• 6: KHOVANSKII, A. G. Fewnomials. American Mathematical Society, Providence, RI, 1991.
• 7: Ariane Péladan-Germa, Testing Identities of Series Defined by Algebraic Partial Differential Equations, Proceedings of the 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.393-407, July 17-22, 1995
• 8: Daniel Richardson, The Uniformity Conjecture, Selected Papers from the 4th International Workshop on Computability and Complexity in Analysis, p.253-272, September 17-19, 2000
• 9: RISCH, R. Algebraic properties of elementary functions in analysis. Amer. Journ. of Math. 4, 101 (1975), 743-759.
• 10: J. Shackle, A differential-equations approach to functional equivalence, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.7-10, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74542]
• 11: SHACKELL, J. Zero-equivalence in function fields defined by algebraic differential equations. Trans. Amer. Math. Soc. 336/1 (1993), 151-172.
• 12: SHACKELL, J., AND VAN DER HOEVEN, J. Complexity bounds for zero-test algorithms. Tech. Rep. 2001-63, Prépublications d'Orsay, 2001.
• 13: VAN DER HOEVEN, J. Automatic asymptotics. PhD thesis, École polytechnique, France, 1997.
• 14: VAN DER HOEVEN, J. Relax, but don't be too lazy. Tech. Rep. 78, Prépublications d'Orsay, 1999. Submitted to JSC.
• 15: VAN DER HOEVEN, J. Complex transseries solutions to algebraic differential equations. Tech. Rep. 2001-34, Univ. d'Orsay, 2001.
• 16: Joris van der Hoeven, Fast evaluation of holonomic functions near and in regular singularities, Journal of Symbolic Computation, v.31 n.6, p.717-743, June 2001 [doi>10.1006/jsco.2000.0474]
• 17: VAN DER HOEVEN, J. Zero-testing, witness conjectures and differential diophantine approximation. Tech. Rep. 2001-62, Prépublications d'Orsay, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Documentation, Standardization