The differential Hilbert function of a differential rational mapping can be computed in polynomial time

ABSTRACT

We present a probabilistic seminumerical algorithm that computes the differential Hilbert function associated to a differential rational mapping. This algorithm explicitly determines the set of variables and derivatives which can be arbitrarily fixed in order to locally invert the differential mapping under consideration. The arithmetic complexity of this algorithm is polynomial in the input size.

REFERENCES

• 1: BAUR, W., AND STRASSEN, V. The complexity of partial derivatives. Theor. Comp. Sc. 22, 3 (1983).
• 2: BOULIER, F. Efficient computation of regular differential systems by change of rankings using Kähler differentials. Preprint 1999-14, Univ. de Lille I, 1999.
• 3: F. Boulier , D. Lazard , F. Ollivier , M. Petitot, Representation for the radical of a finitely generated differential ideal, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.158-166, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220367]
• 4: CAMPBELL, S., AND GEAR, C. The index of general nonlinear DAE's. Numer. Math. 72, 2 (1995), 173-196.
• 5: EISENBUD, D. Commutative algebra with a view toward algebraic geometry. 150 in GTM. Springer, 1994.
• 6: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 7: HEINTZ, J., MATERA, G., AND WAISSBEIN, A. On the time-space complexity of geometric elimination procedures. AAECC 11, 4 (2001), 239-296.
• 8: Evelyne Hubert, Factorization-free decomposition algorithms in differential algebra, Journal of Symbolic Computation, v.29 n.4-5, p.641-662, April/May 2000 [doi>10.1006/jsco.1999.0344]
• 9: JOHNSON, J. Kähler differentials and differential algebra. Annals of Mathematics 89, 1 (1969), 92-98.
• 10: KOLCHIN, E. R. Differential algebra and algebraic groups, vol. 54 of Pure and applied Mathematics. Academic press, New York, 1973.
• 11: MATERA, G. Probabilistic algorithms for geometric elimination. AAECC 9, 6 (1999), 463-520.
• 12: François Ollivier, Standard Bases of Differential Ideals, Proceedings of the 8th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.304-321, August 20-24, 1990
• 13: REID, G., LIN, P., AND WITTKOPF, A. Differential elimination-completion algorithms for DAE and PDAE. Stud. Appl. Math. 106, 1 (2001), 1-45.
• 14: RITT, J. F. Differential algebra. Dover Publ., 1966.
• 15: SADIK, B. A bound for the order of characteristic set elements of an ordinary prime differential ideal and some applications. AAECC 10, 3 (2000), 251-268.
• 16: SEDOGLAVIC, A. A mixed symbolic-numeric method to study prime ordinary differential ideal. Manuscript 2000-04, GAGE laboratory, Jan. 2000. Available at http://www.medicis.polytechnique.fr/~sedoglav.
• 17: Alexandre Sedoglavic, A probabilistic algorithm to test local algebraic observability in polynomial time, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.309-317, July 2001, London, Ontario, Canada [doi>10.1145/384101.384143]
• 18: VALIANT, L. G. Reducibility by algebraic projections. L'enseig. Math. IIe Séries 28, 3-4 (1982), 253-268.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Differential-algebraic equations

General Terms:
Algorithms, Experimentation

Keywords:
differential Hilbert function, differential algebra, seminumerical algorithm