Fast differential eleminination in C: The CDiffElim environment. (English) Zbl 0986.65105
Summary: We introduce the CDiffElim environment, written in C, and an algorithm developed in this environment for simplifying systems of overdetermined partial differential equations by using differentiation and elimination.
This environment has strategies for addressing difficulties encountered in differential elimination algorithms, such as exhaustion of computer memory due to intermediate expression swell, and failure to complete due to the massive number of calculations involved. These strategies include low-level memory management strategies and data representations that are tailored for efficient differential elimination algorithms. These strategies, which are coded in a low-level C implementation, seem much more difficult to implement in high-level general purpose computer algebra systems.
A differential elimination algorithm written in this environment is applied to the determination of symmetry properties of classes of \((n+1)\)-dimensional coupled nonlinear partial differential equations of the form \[ i{\mathbf u}_t+ \nabla^2{\mathbf u}+ (a(t)|{\mathbf x}|^2+{\mathbf b}(t)\cdot{\mathbf x}+ c(t)+ d|{\mathbf u}|^{4/n}){\mathbf u}= \text{\textbf{0}}, \] where \({\mathbf u}\) is an \(m\)-component vector-valued function. The resulting systems of differential equations for the symmetries have been made available on the web, to be used as benchmark systems for other researchers. The new differential elimination algorithm in C, runs on the test suite an average of 400 times faster than our RifSimp algorithm in Maple.
New algorithms, including an enhanced GCD algorithm, and a hybrid symbolic-numeric differential elimination algorithm, are also described.
This environment has strategies for addressing difficulties encountered in differential elimination algorithms, such as exhaustion of computer memory due to intermediate expression swell, and failure to complete due to the massive number of calculations involved. These strategies include low-level memory management strategies and data representations that are tailored for efficient differential elimination algorithms. These strategies, which are coded in a low-level C implementation, seem much more difficult to implement in high-level general purpose computer algebra systems.
A differential elimination algorithm written in this environment is applied to the determination of symmetry properties of classes of \((n+1)\)-dimensional coupled nonlinear partial differential equations of the form \[ i{\mathbf u}_t+ \nabla^2{\mathbf u}+ (a(t)|{\mathbf x}|^2+{\mathbf b}(t)\cdot{\mathbf x}+ c(t)+ d|{\mathbf u}|^{4/n}){\mathbf u}= \text{\textbf{0}}, \] where \({\mathbf u}\) is an \(m\)-component vector-valued function. The resulting systems of differential equations for the symmetries have been made available on the web, to be used as benchmark systems for other researchers. The new differential elimination algorithm in C, runs on the test suite an average of 400 times faster than our RifSimp algorithm in Maple.
New algorithms, including an enhanced GCD algorithm, and a hybrid symbolic-numeric differential elimination algorithm, are also described.
MSC:
| 65N22 | Numerical solution of discretized equations for boundary value problems involving PDEs |
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
| 35G05 | Linear higher-order PDEs |
| 35-04 | Software, source code, etc. for problems pertaining to partial differential equations |
| 65Y15 | Packaged methods for numerical algorithms |
| 68W30 | Symbolic computation and algebraic computation |
Keywords:
differential elimination; differential Gröbner basis; symbolic computation; algorithms; nonlinear partial differential equationsReferences:
| [1] | Benney, D. J.; Roskes, G. J., Wave instabilities, Stud. Appl. Math., 48, 377-385 (1969) · Zbl 0216.52904 |
| [2] | Berkhoer, A. L.; Zakharov, V. E., Self excitation of waves with different polarizations in nonlinear media, Sov. Phys. JETP, 31, 486-490 (1970) |
| [3] | Bluman, G. W.; Kumei, S., Symmetries and Differential Equations. Symmetries and Differential Equations, Applied Mathematical Sciences, 81 (1989), Springer: Springer Berlin · Zbl 0718.35003 |
| [4] | F. Boulier, Some improvements of a lemma of Rosenfeld, 1998, Preprint; F. Boulier, Some improvements of a lemma of Rosenfeld, 1998, Preprint |
| [5] | Boulier, F.; Lazard, D.; Ollivier, F.; Petitot, M., Representation for the radical of a finitely generated differential ideal, (Proc. ISSAC 1995 (1995), ACM Press: ACM Press New York), 158-166 · Zbl 0911.13011 |
| [6] | Brenan, K.; Campbell, S.; Petzold, L., Numerical Solutions of Initial-Value Problems in Differential-Algebraic Equations (1989), Elsevier: Elsevier Amsterdam · Zbl 0699.65057 |
| [7] | Brown, W., On Euclid’s algorithm and the computation of polynomial greatest common divisors, J. ACM, 18, 476-504 (1971) · Zbl 0226.65040 |
| [8] | Buchberger, B., Gröbner bases: An algorithmic method in polynomial ideal theory, (Multidimensional Systems Theory (1985), D. Reidel: D. Reidel Dordrecht), 184-232 · Zbl 0587.13009 |
| [9] | Carrà Ferro, G.; Sit, W., On term-orderings and rankings, (Computational Algebra. Computational Algebra, Lecture Notes in Pure Appl. Math., 151 (1994), Marcel Dekker: Marcel Dekker New York), 31-77 · Zbl 0788.68072 |
| [10] | Clarkson, P., Dimensional reductions and exact solutions of a generalized nonlinear Schrödinger equation, Nonlinearity, 5, 453-472 (1992) · Zbl 0752.35064 |
| [11] | Cormen, T.; Leiserson, C.; Rivest, R., Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge, MA · Zbl 1158.68538 |
| [12] | Fels, M.; Olver, P., Moving coframes. I. A practical algorithm, Acta Appl. Math., 51, 161-213 (1998) · Zbl 0937.53012 |
| [13] | Gagnon, L., Self-similar solutions for a coupled system of nonlinear Schrödinger equations, J. Phys. A: Math. and Gen., 25, 2649-2667 (1992) · Zbl 0754.35156 |
| [14] | Gagnon, L.; Winternitz, P., Lie symmetries of a generalised nonlinear Schrödinger equation. II. Exact solutions, J. Phys. A: Math. and Gen., 22, 469-497 (1989) · Zbl 0707.35145 |
| [15] | Golub, G.; Loan, C. V., Matrix Computations (1996), John Hopkins U. Press: John Hopkins U. Press Baltimore, MD · Zbl 0865.65009 |
| [16] | Grimshaw, R., Slowly varying solitary waves. II. Nonlinear Schrödinger equation, Proc. Roy. Soc. London Ser. A, 368, 377-388 (1979) · Zbl 0416.76014 |
| [17] | Hartley, D.; Tucker, R., A constructive implementation of the Cartan-Kähler theory of exterior differential systems, J. Symbolic Comput., 12, 655-667 (1991) · Zbl 0753.58002 |
| [18] | Ibragimov, N. H., CRC Handbook of Lie Group Analysis of Differential Equations, Vols. I-III (19941996), CRC Press: CRC Press Boca Raton |
| [19] | Janet, M., Sur les systèmes d’équations aux dérivées partielles, J. de Math., 8, 3, 65-151 (1920) · JFM 47.0440.03 |
| [20] | Knuth, D., The Art of Computer Programming: Fundamental Algorithms, Vol. 1 (1997), Addison-Wesley Longman: Addison-Wesley Longman Reading, MA · Zbl 0895.68055 |
| [21] | Knuth, D., The Art of Computer Programming: Seminumerical Algorithms, Vol. 2 (1997), Addison-Wesley Longman: Addison-Wesley Longman Reading, MA · Zbl 0895.68055 |
| [22] | Mansfield, E., Differential Gröbner bases, PhD thesis (1991), Univ. of Sydney |
| [23] | Mansfield, E.; Reid, G.; Clarkson, P., Nonclassical reductions of a \((3+1)\)-cubic nonlinear Schrödinger system, Comput. Phys. Comm., 115, 460-488 (1998) · Zbl 0996.35069 |
| [24] | Monagan, M.; Wittkopf, A., On the design and implementation of Brown’s algorithm over the integers and number fields, (Proc. ISSAC’2000, St. Andrews (2000), ACM Press: ACM Press New York), 215-223 |
| [25] | Oh, M.; Pantelides, C., A modelling and simulation language for combined lumped and distributed parameter systems, Comput. Chem. Engrg., 20, 611-633 (1996) |
| [26] | Olver, P., Applications of Lie Groups to Differential Equations. Applications of Lie Groups to Differential Equations, Graduate Texts in Mathematics, 107 (1993), Springer: Springer Berlin · Zbl 0785.58003 |
| [27] | Olver, P., Equivalence, Invariants, and Symmetry. Equivalence, Invariants, and Symmetry, Graduate Texts in Mathematics (1995), Cambridge University Press · Zbl 0837.58001 |
| [28] | Phillips, O. M., The Dynamics of the Upper Ocean (1977), Cambridge University Press · Zbl 0368.76002 |
| [29] | Pommaret, J.-F., Systems of Partial Differential Equations and Lie Pseudogroups (1978), Gordon and Breach: Gordon and Breach London · Zbl 0418.35028 |
| [30] | Reid, G., Algorithms for reducing a system of PDEs to standard form, determining the dimension of its solution space and calculating its Taylor series solution, European J. Appl. Math., 2, 293-318 (1991) · Zbl 0768.35001 |
| [31] | Reid, G.; Lisle, I.; Boulton, A.; Wittkopf, A., Algorithmic determination of commutation relations for Lie symmetry algebras of PDEs, (Wang, P., Proc. ISSAC’92, Berkeley (1992), ACM Press: ACM Press New York), 63-68 · Zbl 0978.65514 |
| [32] | Reid, G.; Wittkopf, A., Determination of maximal symmetry groups of classes of differential equations, (Proc. ISSAC’2000, St. Andrews (2000), ACM Press: ACM Press New York), 264-272 · Zbl 1326.68367 |
| [33] | Reid, G.; Wittkopf, A.; Boulton, A., Reduction of systems of nonlinear partial differential equations to simplified involutive forms, European J. Appl. Math., 7, 635-666 (1996) · Zbl 0892.35041 |
| [34] | Riquier, C., Les systèmes d’équations aux dérivées partielles (1910), Gauthier-Villars: Gauthier-Villars Paris · JFM 40.0411.01 |
| [35] | Rust, C., Rankings of derivatives for elimination algorithms and formal solvability of analytic partial differential equations, PhD thesis (1998), Univ. Chicago, www-address: www.cecm.sfu.ca/ rust |
| [36] | Rust, C.; Reid, G., Rankings of partial derivatives, (Küchlin, W., Proc. ISSAC’97, Maui (1997), ACM Press: ACM Press New York), 9-16 · Zbl 0960.12003 |
| [37] | Rust, C.; Reid, G.; Wittkopf, A., Existence and uniqueness theorems for formal power series solutions of analytic differential systems, (Dooley, S., Proc. ISSAC’99, Vancouver (1999), ACM Press: ACM Press New York), 105-112 |
| [38] | Schwarz, F., Reduction and completion algorithms for partial differential equations, (Wang, P., Proc. ISSAC’92, Berkeley (1992), ACM Press: ACM Press New York), 49-56 · Zbl 0978.65515 |
| [39] | A. Sedoglavic, A mixed symbolic-numeric method to study prime ordinary differential ideal, www.medicis.polytechnique.fr/gage/notes/2000.html, 2000, Preprint; A. Sedoglavic, A mixed symbolic-numeric method to study prime ordinary differential ideal, www.medicis.polytechnique.fr/gage/notes/2000.html, 2000, Preprint |
| [40] | Seiler, W., Analysis and application of the formal theory of partial differential equations, PhD thesis (1994), Lancaster University |
| [41] | Sommese, A.; Verschelde, J.; Wampler, C., Numerical homotopies to compute generic points on positive dimensional algebraic sets, J. of Complexity, 16, 572-602 (2000) · Zbl 0982.65070 |
| [42] | A. Sommese, J. Verschelde, C. Wampler, Numerical irreducible decomposition using projections from points on the components, Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, 2000, Preprint; A. Sommese, J. Verschelde, C. Wampler, Numerical irreducible decomposition using projections from points on the components, Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, 2000, Preprint · Zbl 1061.68593 |
| [43] | Sulem, C.; Sulem, P. L., The Nonlinear Schrödinger Equation, Self-Focussing and Wave Collapse. The Nonlinear Schrödinger Equation, Self-Focussing and Wave Collapse, Applied Mathematical Sciences, 139 (1999), Springer: Springer Berlin · Zbl 0928.35157 |
| [44] | Talanov, V., Focusing of light in cubic media, JETP Lett., 11, 199-201 (1970) |
| [45] | Trefethen, L., Numerical Linear Algebra (1997), SIAM: SIAM Philadelphia · Zbl 0874.65013 |
| [46] | Wittkopf, A., Efficient implementation of differential elimination algorithms, PhD thesis (2001), Simon Fraser University |
| [47] | Wittkopf, A.; Reid, G., Fast differential elimination algorithms, Technical Report TR-00-06 (2000), Ontario Research Centre for Computer Algebra |
| [48] | Wolf, T., A package for the analytic investigation and exact solutions of differential equations, (Proc. EUROCAL’87, 378 (1987), Springer: Springer Berlin), 479-491 · Zbl 1209.68700 |
| [49] | Zippel, R., Probabilistic algorithms for sparse polynomials, PhD thesis (1979), Massachusetts Inst. of Technology · Zbl 0418.68040 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
