Geometric completion of differential systems using numeric-symbolic continuation

ABSTRACT

Symbolic algorithms using a finite number of exact differentiations and eliminations are able to reduce over and under-determined systems of polynomially nonlinear differential equations to involutive form. The output involutive form enables the identification of consistent initial values, and eases the application of exact or numerical integration methods.Motivated to avoid expression swell of pure symbolic approaches and with the desire to handle systems with approximate coefficients, we propose the use of homotopy continuation methods to perform the differential-elimination process on such non-square systems. Examples such as the classic index 3 Pendulum illustrate the new procedure. Our approach uses slicing by random linear subspaces to intersect its jet components in finitely many points. Generation of enough generic points enables irreducible jet components of the differential system to be interpolated.

REFERENCES

• 1: E.L. Allgower and K. Georg. Numerical path following. In Scientific Computing (Part 2), edited by P.G. Ciarlet and J.L. Lions, pages 3-203. Volume 5 of Handbook of Numerical Analysis, North-Holland, 1997.
• 2: Uri M. Ascher , Linda R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 3: T. Arponen. The complete form of a differential algebraic equation. Helsinki Univ. of Tech. Inst. of Math. Research Rep. Number A438, 2001. Available at http://www.math.hut.fi/reports/
• 4: 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]
• 5: S.L. Campbell and C.W. Gear. The index of general nonlinear DAEs. Numer. Math. 72: 173-196, 1995.
• 6: Robert M. Corless , André Galligo , Ilias S. Kotsireas , Stephen M. Watt, A geometric-numeric algorithm for absolute factorization of multivariate polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.37-45, July 07-10, 2002, Lille, France [doi>10.1145/780506.780512]
• 7: George Corliss , Christèle Faure , Andreas Griewank , Lauren Hascoët , Uwe Naumann, Automatic differentiation of algorithms: from simulation to optimization, Springer-Verlag New York, Inc., New York, NY, 2000
• 8: D. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. Springer, 1996 (2nd Edition).
• 9: M. Giusti and J. Heintz. Kronecker's smart, little black boxes. In Foundations of Computational Mathematics, edited by R.A. DeVore, A. Iserles, and E. Süli. Volume 284 of the London Mathematical Society Lecture Note Series, Cambridge University Press, 2001.
• 10: M. Hausdorf and W.M. Seiler. Perturbation versus differentiation indices. In Computer Algebra in Scientific Computing---CASC'01, edited by V.G. Ganzha, E. W. Mayr and E. V. Vorozhtsov, pages 323-337. (Springer, Berlin) 2001.
• 11: Joos Heintz , Teresa Krick , Susana Puddu , Juan Sabia , Ariel Waissbein, Deformation techniques for efficient polynomial equation solving, Journal of Complexity, v.16 n.1, p.70-109, March 2000 [doi>10.1006/jcom.1999.0529]
• 12: 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]
• 13: C. Lanczos. Applied Analysis. Prentice Hall, 1956.
• 14: G. Lecerf. Une alternative aux méthodes de réécriture pour la résolution des systèmes algébriques. Thèse de doctorat de l'École polytechnique, 2001.
• 15: G. Le Vey. Some remarks on solvability and various indices for implicit differential equations. Numer. Algorithms 19: 127-145, 1998.
• 16: T.Y. Li. Numerical solution of multivariate polynomial systems by homotopy continuation methods. Acta Numerica 6: 399-436, 1997.
• 17: E. Mansfield. Differential Gröbner Bases. Ph.D. thesis, Univ. of Sydney, 1991.
• 18: J.F. Pommaret. Systems of Partial Differential Equations and Lie Pseudogroups. Gordon and Breach Science Publishers, Inc. 1978.
• 19: F. Pritchard and W. Sit. On initial value problems for ordinary DAEs. To appear in J. Symbolic Computation.
• 20: M. P. Quéré , G. Villard, An algorithm for the reduction of linear DAE, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.223-231, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220374]
• 21: G.J. Reid, A.D. Wittkopf and A. Boulton. Reduction of systems of nonlinear partial differential equations to simplified involutive forms. Eur. J. of Appl. Math. 7: 604-635.
• 22: G.J. Reid, P. Lin, and A.D. Wittkopf. Differential elimination-completion algorithms for DAE and PDAE. Studies in Applied Mathematics 106(1): 1-45, 2001.
• 23: P.J. Rabier and W.C. Rheinboldt. A geometric treatment of implicit differential-algebraic equations. Journal of Differential Equations 109: 110-146, 1994.
• 24: S. Reich. Beitrag zur Theorie der Algebrodifferentialgleichungen. Ph.D. dissertation in Engineering, T.U. Dresden. 1989.
• 25: C. J. Rust , G. J. Reid , A. D. Wittkopf, Existence and uniqueness theorems for formal power series solutions of analytic differential systems, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.105-112, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309875]
• 26: 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]
• 27: W.M. Seiler. Analysis and application of the formal theory of partial differential equations. Ph.D. thesis, Lancaster University, 1994.
• 28: W.M. Seiler. Involution and constrained dynamics II: the Faddeev-Jackiw approach. J. Phys. A. 28:7315-7331, 1995.
• 29: W.M. Seiler. Indices and solvability for general systems of differential equations. In Computer algebra in scientific computing---CASC'99, edited by V.G. Ganzha, E. W. Mayr and E. V. Vorozhtsov, pages 365-385. (Springer, Berlin) 1999.
• 30: W.M. Seiler and R.W. Tucker. Involution and constrained dynamics I: the Dirac approach. J. Phys. A. 28:4431-4451, 1995.
• 31: M. Shub , S. Smale, Complexity of Bezout's theorem V: polynomial time, Theoretical Computer Science, v.133 n.1, p.141-164, Oct. 10, 1994
• 32: Andrew J. Sommese, Numerical homotopies to compute generic points on positive dimensional algebraic sets, Journal of Complexity, v.16 n.3, p.572-602, Sept. 2000 [doi>10.1006/jcom.2000.0554]
• 33: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Numerical Decomposition of the Solution Sets of Polynomial Systems into Irreducible Components, SIAM Journal on Numerical Analysis, v.38 n.6, p.2022-2046, 2001 [doi>10.1137/S0036142900372549]
• 34: A.J. Sommese, J. Verschelde, and C.W. Wampler. Numerical irreducible decomposition using projections from points on the components. In Symbolic Computation: Solving Equations in Algebra, Geometry, and Engineering, Volume 286 of Contemporary Mathematics, edited by E.L. Green, S. Hoşten, R.C. Laubenbacher, and V. Powers, pages 37-51. AMS 2001.
• 35: A.J. Sommese, J. Verschelde, and C.W. Wampler. Using monodromy to decompose solution sets of polynomial systems into irreducible components. In Application of Algebraic Geometry to Coding Theory, Physics and Computation, edited by C. Ciliberto, F. Hirzebruch, R. Miranda, and M. Teicher, 297-315, 2001. Proceedings of a NATO Conference, February 25 - March 1, 2001, Eilat, Israel. Kluwer Academic Publishers.
• 36: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Symmetric Functions Applied to Decomposing Solution Sets of Polynomial Systems, SIAM Journal on Numerical Analysis, v.40 n.6, p.2026-2046, 2002 [doi>10.1137/S0036142901397101]
• 37: A.J. Sommese, J. Verschelde, and C.W. Wampler. Numerical irreducible decomposition using PHCpack. To appear in Mathematics and Visualization, edited by M. Joswig and N. Takayama. Springer-Verlag.
• 38: A.J. Sommese, J. Verschelde, and C.W. Wampler. A method for tracking singular paths with application to the numerical irreducible decomposition. In Algebraic Geometry, a Volume in Memory of Paolo Francia, edited by M.C. Beltrametti, F. Catanese, C. Ciliberto, A. Lanteri, C. Pedrini. W. de Gruyter, to appear.
• 39: A.J. Sommese, J. Verschelde, and C.W. Wampler. Advances in polynomial continuation for solving problems in kinematics. In Proc. ASME Design Engineering Technical Conf. (CDROM), Paper DETC2002/MECH34254. Montreal, Quebec, Sept. 29-Oct. 2, 2002.
• 40: A.J. Sommese and C.W. Wampler. Numerical algebraic geometry. In The Mathematics of Numerical Analysis, Volume 32 of Lectures in Applied Mathematics, edited by J. Renegar, M. Shub, and S. Smale, 749-763, 1996. Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics, Park City, Utah, July 17-August 11, 1995, Park City, Utah.
• 41: G. Thomas, Symbolic computation of the index of quasilinear differential-algebraic equations, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.196-203, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.237074]
• 42: J. Tuomela and T. Arponen. On the numerical solution of involutive ordinary differential systems. IMA J. Numer. Anal. 20: 561-599, 2000.
• 43: Jan Verschelde, Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Transactions on Mathematical Software (TOMS), v.25 n.2, p.251-276, June 1999 [doi>10.1145/317275.317286]
• 44: J. Visconti. Numerical Solution of Differential Algebraic Equations, Global Error Estimation and Symbolic Index Reduction. Ph.D. Thesis. Laboratoire de Modélisation et Calcul. Grenoble. 1999.
• 45: A. Wittkopf and G.J. Reid. Fast differential elimination in C: The CDiffElim environment. Computer Physics Communications, 139: 192-217, 2001.