skip to main content
10.1145/1277548.1277599acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

Symbolic-numeric computation of implicit riquier bases for PDE

Published: 29 July 2007 Publication History

Abstract

Riquier Bases for systems of analytic pde are, loosely speaking, a differential analogue of Gröbner Bases for polynomial equations. They are determined in the exact case by applying a sequence of prolongations (differentiations) and eliminations to an input system of pde.
We present a symbolic-numeric method to determine Riquier Bases in implicit form for systems which are dominated by pure derivatives in one of the independent variables and have the same number of pde and unknowns.
The method is successful provided the prolongations with respect to the dominant independent variable have a block structure which is uncovered by Linear Programming and certain Jacobians are non-singular when evaluated at points on the zero sets defined by the functions of the pde. For polynomially nonlinear pde, homotopy continuation methods from Numerical Algebraic Geometry can be used to compute approximations of the points.
We give a differential algebraic interpretation of Pryce's method for ode, which generalizes to the pde case. A major aspect of the method's efficiency is that only prolongations with respect to a single (dominant) independent variable are made, possibly after a random change of coordinates. Potentially expensive and numerically unstable eliminations are not made. Examples are given to illustrate theoretical features of the method, including a curtain of Pendula and the control of a crane.

References

[1]
F. Boulier. Réécriture algébrique dans les systèmes d'équations différentielles en vue d'applications dans les Sciences du Vivant. Habilitation Thesis, 2006.
[2]
F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Representation for the radical of a finitely generated differential ideal. Proc. ISSAC 1995. ACM Press. 158--166, 1995.
[3]
S. Basu, R. Pollack and M. Roy. Algorithms in Real Algebraic Geometry, Springer, 2003.
[4]
S.L. Campbell. High index differential algebraic equations. J. Mech. Struct. and Machines, 23: pp 199--222, 1995.
[5]
R.C. Gunning and H. Rossi. Analytic functions of several complex variables. Prentice-Hall, 1965.
[6]
S. Ilie, R.M. Corless and G. Reid. Numerical solutions of index-1 differential algebraic equations can be computed in polynomial time. Numerical Algorithms, Vol. 41 (2), pp. 161--171, 2006.
[7]
E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms II: Differential Systems. Symbolic and Numerical Scientific Computations, Edited by U. Langer and F. Winkler. LNCS, volume 2630, Springer-Verlag Heidelberg, 2003.
[8]
E. Kolchin. Differential Algebra and Algebraic Groups. Academic Press, New York, 1973.
[9]
S. Krantz and H. Parks. A Primer of Real Analytic Functions. Basler Lehrbücher, 2002.
[10]
K. Krupchyk and J. Tuomela. Shapiro-Lopatinskij Condition for Elliptic Boundary Value Problems. LMS J. Comput. Math. 9 (2006) pp. 287--329.
[11]
K. Krupchyk, W. Seiler and J. Tuomela. Overdetermined Elliptic PDEs. Found. Comp. Math. 6 (2006), No. 3, pp 309--351.
[12]
Y. Lu. Finding all real solutions of polynomial systems. Ph.D. Thesis, University of Notre Dame, 2006 (Submitted).
[13]
J.D. Pryce. A Simple Structure Analysis Method for DAEs. BIT, vol 41, No. 2, pp. 364--394, 2001.
[14]
E. Mansfield. Differential Gröbner Bases. Ph.D. thesis, Univ. of Sydney, 1991.
[15]
G. Reid, C. Smith, and J. Verschelde. Geometric completion of differential systems using numeric-symbolic continuation. SIGSAM Bulletin 36(2):1--17, 2002.
[16]
G. Reid, J. Verschelde, A.D. Wittkopf and W. Wu. Symbolic-Numeric Completion of Differential Systems by Homotopy Continuation. Proc. ISSAC 2005. ACM Press. 269--276, 2005.
[17]
G.J. Reid, P. Lin, and A.D. Wittkopf. Differential elimination-completion algorithms for DAE and PDAE. Studies in Applied Math. 106(1): 1--45, 2001.
[18]
C.J. Rust, Rankings of derivatives for elimination algorithms and formal solvability of analytic partial differential equations, Ph.D. Thesis, University of Chicago, 1998.
[19]
C.J. Rust, G.J. Reid, and A.D. Wittkopf. Existence and uniqueness theorems for formal power series solutions of analytic differential systems. Proc. ISSAC 99. ACM Press. 105--112, 1999.
[20]
F. Schwarz. Janet bases for symmetry groups, in: Groebner bases and applications. London Math. Soc., LNS 251, Cambridge Univ. Press, 221--234, 1998.
[21]
A. Sedoglavic. A probabilistic algorithm to test local algebraic observability in polynomial time. J. Symbolic Computation 33(5): 735--755, 2002.
[22]
W.M. Seiler. Involution - The formal theory of differential equations and its applications in computer algebra and numerical analysis. Habilitation Thesis, Univ. of Mannheim, 2002.
[23]
Pengfei Shi, John McPhee. Symbolic Programming of a Graph-Theoretic Approach to Flexible Multibody Dynamics. Mechanics of Structures and Machines, 30(1), 123--154, 2002.
[24]
A.J. Sommese and C.W. Wampler. The Numerical solution of systems of polynomials arising in engineering and science. World Scientific Press, Singapore, 2005.
[25]
J. Verschelde. Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation. ACM Transactions on Mathematical Software 25(2): 251--276, 1999.
[26]
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.
[27]
A. Wittkopf. Algorithms and Implementations for Differential Elimination. Ph.D. Thesis, Simon Fraser University, 2004.
[28]
Wenyuan Wu and Greg Reid. Application of Numerical Algebraic Geometry and Numerical Linear Algebra to PDE. Proc. of ISSAC'06, pages 345--352, ACM 2006.

Cited By

View all

Index Terms

  1. Symbolic-numeric computation of implicit riquier bases for PDE

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation
    July 2007
    406 pages
    ISBN:9781595937438
    DOI:10.1145/1277548
    • General Chair:
    • Dongming Wang
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 29 July 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. implicit function theorem
    2. jet spaces
    3. linear programming
    4. numerical algebraic geometry
    5. partial differential equation
    6. ranking
    7. riquier bases

    Qualifiers

    • Article

    Conference

    ISSAC07
    Sponsor:
    ISSAC07: International Symposium on Symbolic and Algebraic Computation
    July 29 - August 1, 2007
    Ontario, Waterloo, Canada

    Acceptance Rates

    Overall Acceptance Rate 395 of 838 submissions, 47%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media