Sparse Differential Resultant for Laurent Differential Polynomials

详细信息    查看全文

• 作者：Wei Li (1)
  Chun-Ming Yuan (1)
  Xiao-Shan Gao (1)
  
  1. KLMM ; Academy of Mathematics and Systems Science ; Chinese Academy of Sciences ; Beijing ; 100190 ; China
  
• 关键词：Sparse differential resultant ; Jacobi number ; Poisson product formula ; Differential toric variety ; BKK bound ; Single exponential algorithm ; Primary 12H05 ; 68W30 ; Secondary 14M25 ; 14Q99
• 刊名：Foundations of Computational Mathematics
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：15
• 期：2
• 页码：451-517
• 全文大小：1,155 KB
• 参考文献：1. Berkovich, LM, Tsirulik, VG (1986) Differential resultants and some of their applications. Differentsial鈥檔ye Uravneniya 22: pp. 750-757
  2. Bernshtein, DN (1975) The number of roots of a system of equations. Functional Anal. Appl. 9: pp. 183-185 10.1007/BF01075595" target="_blank" title="It opens in new window">CrossRef
  3. A. Buium and P. J. Cassidy, Differential algebraic geometry and differential algebraic groups, in Selected Works of Ellis Kolchin, with Commentary (H. Bass, A. Buium, and P. Cassidy, eds.), American Mathematical Society, Providence, RI, 1998, pp. 567鈥?36.
  4. Brownawell, WD (1987) Bounds for the degrees in the Nullstellensatz. Annals of Mathematics 126: pp. 577-591 10.2307/1971361" target="_blank" title="It opens in new window">CrossRef
  5. Canny, JF (1990) Generalized characteristic polynomials. Journal of Symbolic Computation 9: pp. 241-250 10.1016/S0747-7171(08)80012-0" target="_blank" title="It opens in new window">CrossRef
  6. Carr脿-Ferro, G (1997) A resultant theory for the systems of two ordinary algebraic differential equations. Appl. Algebra Engrg. Comm. Comput. 8: pp. 539-560 10.1007/s002000050090" target="_blank" title="It opens in new window">CrossRef
  7. M. Chardin, Differential resultants and subresultants, in Lecture Notes in Computer Science: Fundamentals of Computation Theory, 529 (1991), Springer, Berlin, 180鈥?89.
  8. Chou, SC, Gao, XS (1993) Automated reasoning in differential geometry and mechanics: part I. an improved version of Ritt-Wu鈥檚 decomposition algorithm. Journal of Automated Reasoning 10: pp. 161-172 10.1007/BF00881834" target="_blank" title="It opens in new window">CrossRef
  9. Cohn, RM (1983) Order and dimension. Proc. Amer. Math. Soc. 87: pp. 1-6 10.1090/S0002-9939-1983-0677218-6" target="_blank" title="It opens in new window">CrossRef
  10. D. Cox, J. Little, and D. O鈥橲hea, Using Algeraic Geometry, Springer, New York, 1998.
  11. D鈥橝ndrea, C (2002) Macaulay style formulas for sparse resultants. Trans. of Amer. Math. Soc. 354: pp. 2595-2629 10.1090/S0002-9947-02-02910-0" target="_blank" title="It opens in new window">CrossRef
  12. C. D鈥橝ndrea and M. Sombra, A Poisson formula for the sparse resultant, 1310.6617v2" class="a-plus-plus">arXiv:1310.6617v2, 2014.
  13. Eisenbud, D, Schreyer, FO, Weyman, J (2004) Resultants and Chow forms via exterior syzygies. Journal of Amer. Math. Soc. 16: pp. 537-579 10.1090/S0894-0347-03-00423-5" target="_blank" title="It opens in new window">CrossRef
  14. Emiris, IZ (1996) On the complexity of sparse elimination. J. Complexity 12: pp. 134-166 10.1006/jcom.1996.0010" target="_blank" title="It opens in new window">CrossRef
  15. Emiris, IZ, Canny, JF (1995) Efficient incremental algorithms for the sparse resultant and the mixed volume. Journal of Symbolic Computation 20: pp. 117-149 10.1006/jsco.1995.1041" target="_blank" title="It opens in new window">CrossRef
  16. Emiris, IZ, Pan, VY (2005) Improved algorithms for computing determinants and resultants. Journal of Complexity 21: pp. 43-71 10.1016/j.jco.2004.03.003" target="_blank" title="It opens in new window">CrossRef
  17. Gao, XS, Li, W, Yuan, CM (2013) Intersection theory in differential algebraic geometry: generic intersections and the differential Chow Form. Trans. of Amer. Math. Soc. 365: pp. 4575-4632 10.1090/S0002-9947-2013-05633-4" target="_blank" title="It opens in new window">CrossRef
  18. Gelfand, IM, Kapranov, MM, Zelevinsky, AV (1990) Generalized Euler integrals and A-hypergeometric functions. Advances in Mathematics 84: pp. 255-271 10.1016/0001-8708(90)90048-R" target="_blank" title="It opens in new window">CrossRef
  19. Gelfand, IM, Kapranov, M, Zelevinsky, AV (1994) Discriminants. Resultants and Multidimensional Determinants, Boston, Birkh盲user
  20. Golubitsky, O, Kondratieva, M, Ovchinnikov, A, Szanto, A (2009) A bound for orders in differential Nullstellensatz. Journal of Algebra 322: pp. 3852-3877 10.1016/j.jalgebra.2009.05.032" target="_blank" title="It opens in new window">CrossRef
  21. Heintz, J (1983) Definability and fast quantifier elimination in algebraically closed fields. Theoretical Computer Science 24: pp. 239-277 10.1016/0304-3975(83)90002-6" target="_blank" title="It opens in new window">CrossRef
  22. W.聽V.聽D. Hodge and D. Pedoe, Methods of Algebraic Geometry, Volume I, Cambridge Univ. Press, Cambridge, 1968.
  23. W.聽V.聽D. Hodge and D. Pedoe, Methods of Algebraic Geometry, Volume II, Cambridge Univ. Press, Cambridge, 1968.
  24. Hong, H (2001) Ore subresultant coefficients in solutions. Appl. Algebra Engrg. Comm. Comput. 12: pp. 421-428 10.1007/s002000100082" target="_blank" title="It opens in new window">CrossRef
  25. Hubert, E (2000) Factorization free decomposition algorithms in differential algebra. Journal of Symbolic Computations 29: pp. 641-662 10.1006/jsco.1999.0344" target="_blank" title="It opens in new window">CrossRef
  26. Jeronimo, G, Krick, T, Sabia, J, Sombra, M (2004) The computational complexity of the Chow form. Foundations of Computational Mathematics 4: pp. 41-117 10.1007/s10208-002-0078-2" target="_blank" title="It opens in new window">CrossRef
  27. Jouanolou, JP (1991) Le formalisme du r猫sultant. Advances in Mathematics 90: pp. 117-263 10.1016/0001-8708(91)90031-2" target="_blank" title="It opens in new window">CrossRef
  28. Kapranov, M, Sturmfels, B (1992) and A Zelevinsky, Chow polytopes and general resultants. Duke Math. J. 67: pp. 189-218 10.1215/S0012-7094-92-06707-X" target="_blank" title="It opens in new window">CrossRef
  29. Kolchin, ER (1973) Differential Algebra and Algebraic Groups. Academic Press, New York
  30. Kolchin, ER (1992) A problem on differential polynomials. Contemporary Mathematics 131: pp. 449-462 10.1090/conm/131.2/1175849" target="_blank" title="It opens in new window">CrossRef
  31. E.聽R. Kolchin, Differential equations in a projective space and linear dependence over a projective Variety, in Contributions to Analysis: A Colletion of Papers Dedicated to Lipman Bers, Academic Press, New York, 1974, pp. 195-214.
  32. Lando, BA (1970) Jacobi鈥檚 bound for the order of systems of first order differential equations. Trans. Amer. Math. Soc. 152: pp. 119-135
  33. Li, W, Gao, XS (2012) Differential Chow form for projective differential variety. Journal of Algebra 370: pp. 344-360 10.1016/j.jalgebra.2012.07.047" target="_blank" title="It opens in new window">CrossRef
  34. W. Li, X.聽S. Gao, and C.聽M. Yuan, Sparse differential resultant, in Proc. ISSAC 2011, ACM Press, New York, 2011, 225-232.
  35. Z. Li, A subresultant theory for linear differential, linear difference and Ore polynomials, with applications, PhD thesis, Johannes Kepler University, 1996.
  36. Ore, O (1932) Formale theorie der linearen differentialgleichungen. Journal f眉r die Reine und Angewandte Mathematik 167: pp. 221-234
  37. Pedersen, P, Sturmfels, B (1993) Product formulas for resultants and Chow forms. Mathematische Zeitschrift 214: pp. 377-396 10.1007/BF02572411" target="_blank" title="It opens in new window">CrossRef
  38. Renegar, J (1992) On the computational complexity and geometry of the first-order theory of the reals, part I. Journal of Symbolic Computation 13: pp. 255-299 10.1016/S0747-7171(10)80003-3" target="_blank" title="It opens in new window">CrossRef
  39. Reinhart, GM (1999) The Schmidt-Kolchin conjecture. Journal of Symbolic Computation 28: pp. 611-630 10.1006/jsco.1999.0317" target="_blank" title="It opens in new window">CrossRef
  40. Ritt, JF (1935) Jacobi鈥檚 problem on the order of a system of differential equations. Annals of Mathematics 36: pp. 303-312 10.2307/1968572" target="_blank" title="It opens in new window">CrossRef
  41. Ritt, JF (1932) Differential Equations from the Algebraic Standpoint. Amer. Math. Soc, New York
  42. Ritt, JF (1950) Differential Algebra. Amer. Math. Soc, New York
  43. Rueda, SL (2013) Linear sparse differential resultant formulas. Linear Algebra and Its Applications 438: pp. 4296-4321 10.1016/j.laa.2013.01.016" target="_blank" title="It opens in new window">CrossRef
  44. Rueda, SL, Sendra, JR (2010) Linear complete differential resultants and the implicitization of linear DPPEs. Journal of Symbolic Computation 45: pp. 324-341 10.1016/j.jsc.2009.09.003" target="_blank" title="It opens in new window">CrossRef
  45. B. Sturmfels, Sparse elimination theory, in Computational Algebraic Geometry and Commutative Algebra (D. Eisenbud and L. Robbiano, eds.), Cambridge University Press, Cambridge, 1993, pp. 264-298.
  46. Sturmfels, B (1994) On the Newton polytope of the resultant. Journal of Algebraic Combinatorics 3: pp. 207-236 10.1023/A:1022497624378" target="_blank" title="It opens in new window">CrossRef
  47. Wu, WT (1989) On the foundation of algebraic differential polynomial geometry. Journal of Systems Science and Mathematics 2: pp. 289-312
  48. Yang, L, Zeng, Z, Zhang, W (2011) Differential elimination with Dixon resultants. Applied Mathematics and Computation 218: pp. 10679-10690 10.1016/j.amc.2012.04.036" target="_blank" title="It opens in new window">CrossRef
  49. Z.聽Y. Zhang, C.聽M. Yuan, and X.聽S. Gao, Matrix formula of differential resultant for first order generic ordinary differential polynomials, in Computer Mathematics, Springer, Berlin Heidelberg, 2014, pp. 479-503.
  50. Zwillinger, D (1998) Handbook of Differential Equations. Academic Press, San Diego
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Computer Science, general
  Math Applications in Computer Science
  Linear and Multilinear Algebras and Matrix Theory
  Applications of Mathematics
  
• 出版者：Springer New York
• ISSN：1615-3383

文摘

In this paper, we first introduce the concept of Laurent differentially essential systems and give a criterion for a Laurent differential polynomial system to be Laurent differentially essential in terms of its support matrix. Then, the sparse differential resultant for a Laurent differentially essential system is defined, and its basic properties are proved. In particular, order and degree bounds for the sparse differential resultant are given. Based on these bounds, an algorithm to compute the sparse differential resultant is proposed, which is single exponential in terms of the Jacobi number and the size of the system.