%%%%%%%%%%%%%%%%%%%% Included file %%%%%%%%%%%%%%%%%%%%%%% \documentclass{article} %\setlength{\textwidth}{6.7in} %\setlength{\oddsidemargin}{-0.15in} %\setlength{\topmargin}{-0.7in} %\setlength{\textheight}{9.3in} %\newcommand{\TR}{\rm} %\newcommand{\HB}{\sf} %\pagestyle{empty} %\pagestyle{myheadings} %\setcounter{page}{4} \title{Description of Reid's Research Area} \usepackage{html} \begin{document} \begin{latexonly} \maketitle \end{latexonly} \begin{rawhtml}

[Retrieve PostScript Version] [Retrieve DVI Version] . \end{rawhtml} \section*{Introduction} My research has involved the development of algorithms to determine properties of systems of nonlinear partial differential equations. Its current emphasis is on the development of symbolic-numeric algorithms. My research area lies at the intersection of algebraic, geometric and algorithmic methods for differential equations; with computer experimentation spurring theoretical developments, and theory prompting experiment. Applications include algorithmic determination of canonical forms for systems of differential equations which are suitable for their analytical or numerical solution (for example, their solution using directed graphs and the determination of all solutions lying in some finite extension of the rational function field). Another application of my work has been the design of algorithms which can calculate the dimension and structure of Lie symmetry algebras of differential equations. Previous methods for calculating structure depended on integration, a process that is not always guaranteed to succeed. Our Maple implemented programs and extensive documentation are publically available. My most significant recent contributions have been the development of a effective canonical form algorithm for systems of polynomially nonlinear systems of partial differential equations and an effective algorithm for determining the structure of infinite Lie pseudogroups. \section*{Background and Motivation} \subsection*{Background for Linear Systems} The Gauss Algorithm reduces systems of linear algebraic equations to a triangular or standard form. A first guess for an analogous method for linear systems of differential equations is to apply the Gauss algorithm to such systems with their derivatives and dependent variables regarded as unknowns. An example of such a Gauss-reduced form is the system $u_x = y u$, $u_y = u$, for $u(x,y)$ where $u_x$ denotes $\partial u / \partial x$ and $u_y$ denotes $\partial u / \partial y$. Differentiation of the first equation with respect to $y$ and the second with respect to $x$ yields the integrability condition $u_{xy}-u_{yx} = y u_y + u - u_x$ $=0$. When reduced subject to the system this condition becomes $u=0$. Thus generalizing the Gauss Algorithm to systems of linear {\sc pde}s, requires the consideration of their differential consequences. Such a generalization was given by Riquier \cite{Riq10} early this century. In rough terms, for linear systems his algorithm repeats the steps of Gauss reducing the system, calculating and reducing its integrability conditions, adjoining nontrivial integrability conditions to the system, until there are no nontrivial integrability conditions. A number of such algorithms have been implemented (see \cite{Sch85,Top89,BocBro89} and the extensive bibliography of our paper \cite{ReiWitBou96}). Our standard form algorithm \cite{Rei91a} uses similar principles to produce a coordinate dependent standard form of linear system of differential equations. The reduced form produced by ours and Riquier's algorithms does not solve such systems. However it does provide a count of the number of parameters in their local analytic solutions \cite{Sch92}. It can substantially simplify them, and can be used to test whether a differential expression is a consequence of the system. It also yields a form of the system to which local existence-uniqueness theorems can be applied. These theorems generalize the Cauchy-Kovaleskaya Theorem \cite{Tho29,Tho31,Kov75}. Such algorithms have proved their worth in simplifying complicated overdetermined systems of linear {\sc pde}s; especially those arising in the Lie symmetry analysis of physical {\sc pde}s. They are becoming a standard part of computer algebra packages for simplifying and solving linear {\sc pde}s (see the references in \cite{ReiWitBou96} and especially those in the review article \cite{Her94}). \subsection*{Buchberger's algorithm for polynomially nonlinear equations} We briefly discuss Buchberger's algorithm, which has led to a revolution in algorithmic methods and applications \cite{BecWei93} for nonlinear mathematics. Consider the system of polynomial equations: $x^2 + yz - 2 = 0$, $xz + y^2 - 3 = 0$, $xy + z^2 - 5 = 0$. Application of the method requires a ranking of monomials. One possible choice is the lexicographic ranking: $x^ay^bz^c \prec x^iy^jz^k$ iff the first nonzero entry of $(i-a,j-b,k-c)$ is positive. Thus $1$ $ \prec$ $z $ $\prec$ $ z^2$ $ ... $ $ \prec$ $ y$ $ \prec$ $ yz$ $ \prec yz^2 $ $\prec$ $...$ etc. Buchberger's algorithm proceeds by computing so-called S-polynomials between pairs of polynomials. For example the S-polynomial of the first two polynomials is $z(x^2+yz-2)-x(xz+y^2-3)$ since $x^2z$ is the lowest common multiple of their leading monomials $x^2$ and $xz$. The result is then reduced with respect to the system. If all the S-polynomials vanish after reduction then the algorithm has terminated with the system in the form of a Gr\"obner Basis. Otherwise the nontrivial reduced S-polynomials are appended to the system and the process is repeated. The resulting Gr\"obner Basis (expressed as equations) for our example is: $361 x - 88 z^7 + 872 z^5 - 2690z^3 + 2375 z = 0$, $361 y + 8 z^7 + 52 z^5 - 740 z^3 + 1425 z = 0$, $8 z^8 - 100 z^6 + 438 z^4 - 760 z^2 + 361 =0$. The above triangularized form is convenient for predicting the existence of, and for bounding the number of the system's solutions. It is also convenient for numerically (or exactly) solving the system. Such properties reflect valuable characteristics of Gr\"obner Bases in general, although of course polynomials of degree greater than four cannot always be solved exactly. The Buchberger algorithm also gives a decision method for the ideal membership problem \cite{BecWei93,Buc65}. \subsection*{Differential Algebra} Ritt \cite{Rit50} introduced differential algebra, the algebraic study of systems of polynomially nonlinear {\sc pde}s, and this work was extensively developed by Kolchin \cite{Kol50}. Attempts to develop differential analogues of Buchberger's algorithm for systems of polynomially nonlinear {\sc pde}s have encountered considerable difficulties. Carr\`{a}-Ferro \cite{Car87} and Ollivier \cite{Oll91} gave definitions of such differential Gr\"obner Bases ({\sc dgb}s) and methods (differential Buchberger algorithms) for their attempted construction. It was also shown that these bases could be infinite (unlike the case for polynomial algebraic equations and linear {\sc pde} systems). Ollivier \cite{Oll91} gave a finite-step method which could construct a {\sc dgb} up to a given order of derivative (even when the {\sc dgb} was infinite). But criteria were not given for determining when the {\sc dgb} had been constructed up to the given order. In a breakthrough work, Mansfield \cite{Man91} gave an algorithm (and a computer-algebra implementation) which used pseudo-reduction instead of reduction to attempt to construct {\sc dgb}s. Her algorithm always terminates but not necessarily with the output system as a {\sc dgb}. She initiated the systematic study of the conditions for obtaining a {\sc dgb}. These conditions entail the analysis of the coefficients which may have to be inverted in the pseudo-division and pseudo-differential reduction used by her algorithm. Her algorithm has proved valuable in applications \cite{ClaMan94}. Recently, Boulier et. al. \cite{BLOP95} gave an algorithm which performs binary branching on the coefficients above. In breakthrough work, they interpreted and rigorously proved that the resulting system of cases, gives a representation of the {\it radical of the differential ideal} generated by the system (but not the differential ideal). Besides the theoretical difficulties mentioned above, there are the practical difficulties of designing efficient algorithms. Buchberger's Algorithm, has been shown to be of high (double-exponential) complexity \cite{BecWei93}, in comparison to the low polynomial complexity of the Gauss Algorithm. Since new unknowns are continually introduced in the differential analogues of such algorithms, their complexity is even worse. Thus practical implementation is a vital concern. In summary, the above methods aim to reduce systems of algebraic equations or {\sc pde}s to desirable forms using algorithmically executable operations. Such operations include differentiation and rational operations, but not integration. Desirable forms include normal or standard forms that can solve membership problems (recognise when a given expression is a consequence of a system). Such forms should be easier to solve using numerical or analytical methods. Desirable features include being able to apply existence and uniqueness theorems to such forms and determine bounds on the number of their solutions. These are key goals in our development of algorithms for {\sc pde}s. \subsection*{Applications to linear overdetermined systems of PDE} In the past two decades there has been rapid development in methods for gaining insight into a given physical {\sc pde} by formulating auxiliary overdetermined systems whose solutions determine features of the given {\sc pde}. The auxiliary overdetermined system of {\sc pde}s for the infinitesimal Lie symmetries of a given {\sc pde} can be automatically produced by many symbolic programs \cite{Her94}, and may contain thousands of {\sc pde}s. Other symbolic programs have been found to be very useful for simplifying and often solving these systems. Applications of Lie symmetries include the determination of invariant or similarity solutions, B\"acklund transformations and soliton solutions. We contributed to this area with our Standard Form package \cite{ReiWit93}. There has been considerable activity analysing properties of physical {\sc pde}s through generalizations of Lie's methods \cite{BluCol69,ClaMan94}. Often the associated overdetermined systems are nonlinear. Thus systematic methods for simplifying large nonlinear systems are needed. Few programs and methods have been developed in this area compared to the well-developed theory, methods and implemented algorithms for linear systems. This motivated us to develop the {\it rif\/} algorithm for simplifying and determining properties of such systems. \section*{Differential Elimination Completion Algorithms for PDE} \subsection*{The Standard Form Package for Linear Systems} The {\it rif\/} algorithm is a generalization of the Standard Form Algorithm \cite{Rei91a} for simplifying linear systems to a coordinate-dependent ordered canonical form. The {\it Long Guide to the Standard Form Package} is 90 page manual \cite{ReiWit93} which documents our algorithms and provides illustrative examples of their use. In \cite[\S8]{ReiWit93} we describe the Standard Form Algorithm's strategy for reducing large systems of {\sc pde}s to standard form. Upon input into the Standard Form Algorithm a system of {\sc pde}s is divided into 4 classes: one-term {\sc pde}s (e.g. $\eta_{xxy} = 0$), `easy' {\sc pde}s, {\sc pde}s which are nonlinear in their highest derivative, and unclassified {\sc pde}s. These classes are updated at each iteration. User defined strategy parameters control the flow of {\sc pde}s between these lists by setting criteria for `easy' or desirable {\sc pde}s. Extreme settings include the greedy and conservative settings. This divide and conquer strategy, which only applies the algorithm to an easy piece of the system at a time, has been key to our success in treating large systems. User controlled interface information helps trace expression swell. To facilitate interactive use there is a storage option which allows a current copy of the system to be stored to disk at each major iteration of the Standard Form Algorithm. In \cite[\S9]{ReiWit93} we give the example of reduction of the determining system for infinitesimal symmetries of the Magneto-Hydrodynamic ({\sc mhd}) equations to standard form. The original system contains more than 2000 {\sc pde}s in 12 independent and 12 dependent variables. The reduced system contains 133 equations, of which 104 are one-term {\sc pde}s, It was automatically integrated using the Taylor expansion algorithm. An implemented strategy is given for systems of {\sc pde} with unspecified functions or parameters. These yield classification problems - problems where a tree of cases corresponding to different values of the parameters or forms of the functions have to be treated separately. A nontrivial example of group classifying a family of nonlinear telegraph equations is given in \cite[\S9]{ReiWit93} and in \cite{Rei91b}. In the manual, interfaces between our packages and the following packages are described: the Maple Exterior Forms package Liesymm; the Macsyma package symmgrp.max and Hickman's Maple package Symmetry. All these packages automatically produce determining systems for infinitesimal symmetries of {\sc pde}s. We are developing such interfaces to avoid unnecessarily duplicating the work of others. \subsection*{The Reduced Involutive Form Algorithm for Nonlinear Systems} The {\it rif\/} algorithm does not reduce a system of {\sc pde}s to a Differential Gr\"obner Basis. It reduces systems of nonlinear analytic {\sc pde}s to a (reduced involutive) form which is simply related to the involutive form of geometric approaches \cite{SchSeiCal92,Pom78}. To apply the algorithm a ranking of derivatives is first specified. An example of such a ranking is: $u \prec u_x$ $ \prec u_y$ $ \prec u_{xx}$ $\prec u_{xy} \prec ...$. Then any {\sc pde} is either linear or nonlinear in its largest or leading derivative with respect to the ranking. The {\it rif\/} algorithm performs linear eliminations amongst the leading linear {\sc pde}s in the same way as the standard form algorithm in the case of linear systems. When any leading nonlinear {\sc pde} is differentiated with respect to an independent variable it becomes linear in its leading derivative. Integrability conditions are calculated in the usual (linear) way across leading linear {\sc pde}s. The {\it rif\/} algorithm terminates when no {\em new} equations were generated relative to the given system. We defined `new' geometrically: an equation is new if it lowers the dimension of the existing system regarded as a submanifold of its jet space. The {\it rif\/}-form of a system is also required to satisfy a constant rank condition. An effective realization of the {\it rif\/} algorithm was given for polynomial {\sc pde} systems. The resulting {\it radical\_rif\/} algorithm realized the constant rank condition by using the algorithms \cite{GiaTraZac89} for effective construction of the radical of the polynomial ideal generated by the system (see \cite[\S5]{ReiWitBou94} for a proof). During the Gaussian elimination phase of the algorithm, pivoting can occur, and in general a finite tree of cases has to be considered. Independently the team \cite{BLOP95} gave a reduction algorithm for polynomially (but not analytic) nonlinear {\sc pde} systems which gives a representation of the radical of a finitely generated differential ideal. This algorithm yields cases based on inequations which are similar to the pivot conditions in our method. This work underwent considerable theoretical development in Colin Rust's thesis \cite{Rus98}. He introduced a family of algebraic variations of the {\it rif\/} algorithm. Rust's Relative Riquier bases, only need ideal membership testing, to obtain formal existence and uniqueness theorems, rather than radical ideal membership testing. To test the practical feasibility of our idea we applied a preliminary implementation of our algorithm to a nonlinear system of 856 {\sc pde}s in 8 independent and 8 dependent variables, arising in the application of the `nonclassical method' to a coupled nonlinear Schr\"odinger ({\sc cnls}) system. The {\it rif}-form of the system was simple enough for its exact solution to be obtained and new truly nonclassical vector fields obtained \cite[\S6]{ReiWitBou94}. In joint work with Mansfield and Clarkson we performed an extensive analysis of the nonclassical reductions of the {\sc cnls} system, which appears in \cite{ManReiCla98}. There has been considerable interest in explicit solutions that result from such reductions of nonlinear Schr\"odinger equations due to commercial applications involving the transmission of optical solitons and quasi-solitons through fibre-optic cables. \section*{Determination of the Size and Structure of Invariance Groups of PDE} \subsection*{Finite parameter Lie groups of symmetries of PDEs} The auxiliary systems of overdetermined linear {\sc pde}s for infinitesimal symmetries of a given physical {\sc pde} can be produced by many effective implementations of an algorithm due to Lie. The research in \cite{Rei90a,Rei90b,Rei91b,RLBW92,LisReiBou95,LisRei97}, has focused on exploiting the standard form of these determining systems to give algorithms for effectively calculating properties of symmetry groups of differential equations. A symmetry of a {\sc pde} maps solutions to solutions; and hence can sometimes produce new solutions from known solutions. Symmetries can reduce the dimensionality of physical problems. (The universal covering groups of) Lie groups are determined up to isomorphism by the structure constants of their Lie algebras. This structure determines geometric properties of differential equations and can enable one to predict if an {\sc ode} can be reduced to quadrature amongst other applications. A necessary condition that two equations are related by a change of variables is that their symmetry groups have the same structure. Explicit construction of the symmetries, change of variables or the reduction of order of an {\sc ode} can be difficult. Our algorithms for calculating size and structure of symmetry groups help forecast the success of such work without first having to carry it out. Traditionally, to determine the form, size and structure of finite parameter Lie symmetry groups of {\sc pde}s, their infinitesimal determining systems are first integrated. This process is not always guaranteed to succeed. If successful the explicit forms of the solutions are substituted into the Lie algebra's commutation relations, and the structure constants of the algebra are determined. In \cite{Rei90b,Rei91b} we gave the first automatic algorithm which did not require such integrations to determine the size and structure of finite parameter symmetry groups of symmetries of {\sc pde}s. Their infinitesimal determining system was reduced to standard form and the infinitesimals expanded in Taylor series. The method was very inefficient and no bound was given for the order to which the Taylor expansion had to be taken to determine the structure constants. Independently Schwarz \cite{Sch92} gave an integration-free algorithm which could determine the size but not the structure of such groups. In other related work Karlhede and MacCallum (Gen. Rel. and Gravitation 14 (1982) 673-682) used Cartan's Method of Equivalence to determine the structure of finite parameter isometry groups of Riemannian spaces. In \cite{RLBW92} we presented an effective and efficient algorithm for calculating structure which bypassed cumbersome Taylor expansions. The key idea of the algorithm was to calculate in the space of initial data of the system; rather than the generally incalculable space of solutions of the system. However our algorithm \cite{RLBW92} was not able to calculate structure of infinite Lie pseudogroups of symmetries of {\sc pde}s. As a generalization of Lie groups to the infinite case, such infinite pseudogroups are subject to severe practical and theoretical difficulties. In particular it is difficult to define them in a way which is independent from the space on which they act. Nevertheless, infinite pseudogroups are objects that appear in applications (e.g. the pseudogroup of local conformal transformations and the pseudogroup of local volume preserving diffeomorphisms). \subsection*{Infinite Lie pseudogroups} We have already discussed our effective methods for calculating the structure constants of finite dimensional Lie symmetry algebras of {\sc pde}s. Although he was optimistic Lie was unable to extend his infinitesimal structure theory to an infinitesimal structure theory of infinite parameter Lie pseudogroups. Cartan developed a structure theory of such infinite pseudogroups. However this structure theory is difficult to apply to physical {\sc pde}s because it requires the analysis of associated overdetermined (pseudogroup) determining systems which are often highly nonlinear and can be very large (e.g. the pseudogroup defining system for the KP equation occupies 30 megabytes when generated automatically by computer). In comparison Lie's method yields infinitesimal determining systems which are linear and generally much smaller. My first effort \cite{ReiLisBou96} towards a practical algorithm for calculating Cartan structure of infinite Lie pseudogroups of {\sc pde}s was a hybrid Lie-Cartan algorithm. To apply the method the infinitesimal determining system is reduced to standard form. This standard form is used to predict a model of the pseudogroup defining system. By requiring the model system to admit the infinitesimal symmetries we obtain a system of {\sc pde}s for the unspecified functions in the model. Cartan's algorithm is then run on the model system subject to this differential characterization. Our success in calculating Cartan structure in examples using this method inspired Lisle to conjecture an infinitesimal form of the method. This infinitesimal method was rigorously justified \cite{LisReiBou95,LisRei97} for Lie pseudogroups of transitive type using the theory of Singer and Sternberg \cite{SinSte65}. In summary we obtained an effective algorithm which from the infinitesimal determining system can determine whether a pseudogroup of symmetries is isomorphic to a transitive pseudogroup. If so, then the algorithm can determine the Cartan structure of the pseudogroup. We applied a preliminary implementation of this algorithm to physical {\sc pde}s with infinite pseudogroups, including the KP and Liouville equations. \section*{Solving PDEs} In \cite{ReiBou91} the standard form of a system of {\sc pde}s is used to construct a directed graph, which is then used as the basis for an algorithm for the integration of the system. In \cite{ReiMck93} the standard form of a system of linear {\sc pde}s is used as the basis of an algorithm to recursively solve systems of linear {\sc pde}s in their coefficient field by decoupling and solving ``{\sc ode}s''. As an application of this algorithm we show that: {\it If the solution space of a system of linear {\sc pde}s is finite-dimensional and the coefficients of the system are all rational functions of the system's independent variables, then all rational function solutions of the system can be determined.} \begin{thebibliography}{??} % The second bracketed item above is inserted for the % purpose of defining the space to be left for the reference % numbers. \bibitem{AraShaJan74} Ara\v\i s, E.A., V.P. \v Sapeev and N.N. Janenko. 1974. {\em Realization of Cartan's method of exterior differential forms on an electronic computer}, Sov. Math. Dokl. {\bf 15}(1) 203--205. \bibitem{AusMac63} Auslander, L. and R.E. MacKenzie. 1963. Introduction to Differentiable Manifolds. (McGraw--Hill, New York). \bibitem{BluCol69} Bluman, G.W. and J.D. Cole. 1969. {\em The general similarity solution of the heat equation}, J. Math. Mech. {\bf 18} 1025--1042. \bibitem{BluKum89} Bluman, G.W. and S. Kumei. 1989. Symmetries and Differential Equations. (Springer Verlag, New York). \bibitem{BLOP95} {Boulier, F., D. Lazard, F. Ollivier} and {M. Petitot}. 1995. Representation for the radical of a finitely generated differential ideal. Proc. ISSAC 1995. ACM Press. 158--166. \bibitem{BreCamPet89} Brenan, K., S. Campbell and L. Petzold. 1989. Numerical Solutions of Initial-Value Problems in Differential-Algebraic Equations. (Elsevier Science Publishers, North-Holland). \bibitem{BC3G} Bryant, R.L., S.S. Chern, R.B. Gardner, H.L. Goldschmidt and P.A. Griffiths. 1991. Exterior Differential Systems, Mathematical Sciences Research Institute Publications {\bf 18} (Springer Verlag, New York). \bibitem{BecWei93} Becker, T., V. Weispfenning. 1993. Gr\"obner bases: a computational approach to commutative algebra. (Springer Verlag, New York) \bibitem{BocBro89} Bocharov, A.V. and M.L. Bronstein. 1989. {\em Efficiently implementing two methods of the geometrical theory of differential equations: an experience in algorithm and software design}, Acta Appl. Math. {\bf 16} 143--166. \bibitem{Buc65} Buchberger, B. 1965. An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal (German), PhD. Thesis, Univ. of Innsbruck, Math. Inst. \bibitem{Car87} Carr\`a-Ferro, G. 1987. {\em Gr\"obner Bases and Differential Algebra,} Lecture Notes in Comp. Sci. {\bf 356} 128--140. \bibitem{CarDuz93} Carr\`a-Ferro, G. and S.V. Duzhin. 1993. Differential-algebraic and differential-geometric approach to the study of involutive symbols. In {\em Modern Group Analysis: Advanced Analytical and Computational Methods in Mathematical Physics}. Edited by N.H. Ibragimov, M. Torrisi and A. Valenti. 93--99. (Kluwer, Dordrecht). \bibitem{CarSit93} Carr\`a Ferro, G. and W.Y. Sit. 1993. {\em On Term-Orderings and Rankings}, Lecture Notes in Pure and Applied Math., Computational Algebra, Dekker, {\bf 151}. \bibitem{CarMcL87} Carminati, J. and R.G. McLenaghan. 1987. {\em An explicit determination of the space-times on which the conformally invariant scalar wave equation satisfies Huygens' principle. --- Part II: Petrov type D space-times\/}. Ann. Inst. Henri Poincar\'e. {\bf 47} (4) 337--354. \bibitem{Car04} Cartan, \'E.J. 1904. Sur la structure des groupes infinis de transformations. {\em Oeuvres Compl\`{e}tes} Part~II, Vol.~2, 571--714. (Gauthier-Villars, Paris). \bibitem{Car34} Cartan, \'E.J. 1937. Les probl\`{e}mes d'\'{e}quivalence. {\em Oeuvres Compl\`{e}tes} Part~II, Vol.~2, 1311--1334. (Gauthier-Villars, Paris). \bibitem{Car37} Cartan, \'E.J. 1937. La structure des groupes infinis. {\em Oeuvres Compl\`{e}tes} Part~II, Vol.~2, 1335--1384. (Gauthier-Villars, Paris). \bibitem{Car46} Cartan E. 1946. {\em Les Syst\`emes Diff\'{e}rentiels Ext\'{e}rieur et leurs Applications G\'{e}ometrique}\, (Hermann, Paris). \bibitem{ClaKru89} Clarkson, P.A. and M.D. Kruskal. 1989. {\em New similarity solutions of the Boussinesq equation}, J. Math. Phys. {\bf 30} 2201--2213. \bibitem{ClaMan93} Clarkson, P.A. and E.L. Mansfield. 1994. {\em Algorithms for the Nonclassical Method of Symmetry Reductions}, SIAM J. Appl. Math. {\bf 54}: 1693--1719. \bibitem{ClaMan94} Clarkson, P.A. and E.L. Mansfield. 1994. {\em On a shallow water wave equation}, Nonlinearity. {\bf 7} 975--1000. \bibitem{ManReiCla98} Mansfield, E.L., G.J. Reid and P.A. Clarkson. 1998, {\it Nonclassical Reductions of a 3+1-Cubic Nonlinear Schr\"odinger System}, Computer Physics Communications {\bf 115}, (in press). 44 single-spaced pages in \LaTeX. \begin{rawhtml} [Retrieve PostScript] . \end{rawhtml} \bibitem{CziThi92} Czichowski, G. and M. Thiede. 1992 {\em Gr\"obner Bases, Standard Forms of Differential Equations and Symmetry Computation\/}, Seminar Sophus Lie Darmstadt-Erlangen-Greifswald-Leipzig. \bibitem{Ehr50} Ehresmann, C. 1950. {\em Les connexions infinit\'esimales dans un espace fibr\'e diff\'erentiable}, Colloque de topologie (espaces fibr\'es) 29-55, Bruxelles. \bibitem{GMMSJ81} Gan$\check{\mbox{z}}$a, V.G., S.V. Mele$\check{\mbox{s}}$ko, F.A. Murzin, V.P. $\check{\mbox{S}}$apeev and N.N. Janenko. 1981. {\em Realization on a computer of an algorithm for studying the consistency of systems of partial differential equations}, Sov. Math. Dokl. {\bf 24}(1) 638--640. \bibitem{GeaPet84} Gear, C.W. and L. Petzold. 1984. {\em ODE methods for the solution of differential/algebraic systems}, SIAM J. Numer. Anal. {\bf 21} 716-728. \bibitem{Gea90} Gear, C.W. 1990. {\em Differential algebraic equations, indices, and integral algebraic equations}, SIAM J. Numer. Anal. {\bf 27} 1527-1534. \bibitem{GedCzaLab92} Geddes, K. O., S. R. Czapor, and G. Labahn. 1992. Algorithms for computer algebra. (Kluwer Academic Publishers). \bibitem{GiaTraZac89} Gianni, P., B. Trager and G. Zacharias. 1989. Gr\"obner Bases and Primary Decomposition of Polynomial Ideals, In {\em Computational Aspects of Commutative Algebra}. Edited by L. Robbiano. 15--33. (Academic Press, New York). \bibitem{Gol67} Goldschmidt, H. 1967. {\em Integrability Criteria for Systems of Partial Differential Equations}, J. Diff. Geom. {\bf 1} 269--307. \bibitem{GunRos65} Gunning, R.C. and H. Rossi. 1965. Analytic Functions of Several Complex Variables. (Prentice--Hall, London). \bibitem{HaiLubRoc89} Hairer, E., C. Lubich and M. Roche. 1989. The Numerical Solution of Differential-Algebraic Systems by Runge-Kutta Methods. Lecture Notes in Math. {\bf 1409} (Springer Verlag, New York). \bibitem{Har97} Hartley, D. 1997. {\em EDS: A REDUCE package for exterior differential systems} Comp. Phys. Comm. {\bf 100}: 177--194. \bibitem{Her94} Hereman, W. 1994. {\em Review of symbolic software for the computation of Lie symmetries of differential equations.\/} Euromath Bull., {\bf 1} 45--79. \bibitem{Hic93} Hickman, M. 1993. {\em The Use of Maple in the Search for Symmetries},\, Research Report no. 77, Department of Mathematics\, (University of Canterbury, Christchurch, New Zealand). \bibitem{Hud87} Hudson, A. 1987. {\em Symbolic Computation of Involutivity of PDES}, Masters Thesis, University of Sydney. \bibitem{Jan20} Janet, M. 1920. {\em Sur les syst\`emes d'\'equations aux d\'eriv\'ees partielles\/}, J. de Math {\bf 3} 65--151. \bibitem{Kah34} K\"ahler, E. 1934. Einf\"uhrung in die Theorie der Systeme von Differentialgleichungen. (B. G. Teubner, Leipzig). \bibitem{Ken77} Kendig, K. 1977. Elementary Algebraic Geometry. (Springer-Verlag, New York). \bibitem{Kol50} Kolchin, E.R. 1950. Differential Algebra and Algebraic Groups. (Academic Press, New York). \bibitem{Kov75} Kovalevskaya, S. 1875. {\em Zur Theorie der Partiellen Differentialgleichungen}, J. Reine Agnew. Math. {\bf 80} 1--32. \bibitem{KSMH80} Kramer, D., H. Stephani, H. MacCallum, and E. Herlt. 1980. {\em Exact solutions of Einstein's field equations}, Deutscher Verl. d. Wiss. (Berlin). \bibitem{Kur57} Kuranishi, M. 1957. {\em On E. Cartan's prolongation theorem of exterior differential systems}, Amer. J. Math., {\bf 79} 1--47. \bibitem{LisRei97} Lisle, I.G. and G. J. Reid. 1998. {\it Geometry and structure from infinitesimal defining equations}, Journal of Symbolic Computation {\bf 26}, 355--379. \begin{rawhtml} [Retrieve PostScript] . \end{rawhtml} \bibitem{LisReiBou95}Lisle, I.G., G.J. Reid and A. Boulton. 1995. {\it Algorithmic determination of the structure of infinite symmetry groups of differential equations}, in Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation (acm press, New York). \bibitem{Lew57} Lewy, H. 1957. {\em An example of a smooth linear partial differential equation without solution}, Ann. Math. {\bf 66} 155--158. \bibitem{Man91} Mansfield, E. 1991. {\em Differential Gr\"{o}bner Bases}, Ph.D Thesis, University of Sydney. \bibitem{Man92} Mansfield, E. 1996. {\em A simple criterion for involutivity\/}, J. London Math. Soc. {\bf 54}: 323--345. \bibitem{ManFac92} Mansfield, E.L. and E.D. Fackerell. 1993 {\em Differential Gr\"obner Bases}, Preprint 92--108\, School of Mathematics, Physics, Computer Science, and Electronics\, (Macquarie University, Sydney, Australia, 1992). \bibitem{Oak94} Oaku, T. 1994. {\em Algorithms for finding the structure of solutions of linear partial differential equations}, In Proc. ISSAC '94. \bibitem{Oll91} Ollivier, F. 1991. {\em Standard bases of differential ideals}, Lecture Notes in Comp. Sci., {\bf 508} 304--321. \bibitem{Olv93} Olver, P.J. 1993. Application of Lie Groups to Differential Equations. (Springer Verlag, New York). Second Edition. %\bibitem{Olvweak} Olver, P.J. 19??.Weak Symmetries article. \bibitem{Ovs82} Ovsiannikov, L.V. 1982. Group analysis of differential equations. (Academic Press, New York). \bibitem{Pom78} Pommaret, J. F. 1978. Systems of Partial Differential Equations and Lie Pseudogroups. (Gordon and Breach science publishers, Inc.) \bibitem{Rei90a} Reid, G.J. 1990. In V. Hussin, {\em Algorithmic Determination of Lie Symmetry Algebras of Differential Equations},\, {\em Lie Theory, Differential Equations and Representation Theory}, Proc. Annual Seminar of the Canadian Math. Soc.\, (Les Publications de Centre de Recherches Math\'{e}matiques, Montr\'{e}al, Canada) 363. \bibitem{Rei90b} Reid, G.J. 1990, {\it A triangularization algorithm which determines the Lie symmetry algebra of any system of PDEs}, J. Phys. A: Math. Gen. {\bf 23}, 853-859. \bibitem{Rei91a} Reid, G.J. 1991. {\em Algorithms for reducing a system of PDEs to standard form, determining the dimension of its solution space and calculating its Taylor series solution\/}, Euro. J. Appl. Math. {\bf 2} 293--318. \bibitem{Rei91b} Reid, G.J. 1991. {\em Finding abstract Lie symmetry algebras of differential equations without integrating determining equations}, Euro. J. Appl. Math. {\bf 2} 319--340. \bibitem{ReiBou91} G. J. Reid and A. Boulton (1991), {\it Reduction of systems of differential equations to standard form and their integration using directed graphs}, in Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, edited by S. M. Watt, 308-312 (acm press, Bonn). \bibitem{ReiWitLin96} Reid, G.J., A. D. Wittkopf and P. Lin. 1996. {\em Diffential-elimination completion algorithms for DAE and PDAE}. Revised for Stud. in Appl. Math. \bibitem{ReiLisBou96} Reid, G.J., I.G. Lisle, A. Boulton. {\em Characterising Lie Equations by their Infinitesimal Symmetries}, preprint. \bibitem{RLBW92} Reid, G.J., I.G. Lisle, A. Boulton and A. D. Wittkopf. 1992. {\em Algorithmic determination of commutation relations for Lie symmetry algebras of PDEs}, in: Proc. ISSAC '92, Berkeley, California, Ed.: P.S. Wang\, (ACM Press, New York, 1992) 63-68. \bibitem{ReiMck93} Reid, G.J., and D.K. McKinnon. 1993. {\em Solving systems of linear PDEs in their coefficient field by recursively decoupling and solving ODEs}, Preprint, Department of Mathematics, (University of British Columbia, Vancouver, Canada). \bibitem{ReiWitBou94} Reid, G.J., A. D. Wittkopf and A. Boulton. 1994. {\em Reduction of systems of nonlinear partial differential equations to simplified involutive forms}. IAM Tech. Report 14. Univ. of Brit. Col. \begin{rawhtml} [Retrieve PostScript] . \end{rawhtml} \bibitem{ReiWitBou96} Reid, G.J., A. D. Wittkopf and A. Boulton. 1996. {\em Reduction of systems of nonlinear partial differential equations to simplified involutive forms}. Eur. J. of Appl. Math. {\bf 7} 635-637. \bibitem{ReiWeiWit93} Reid, G.J., D.T. Weih and A.D. Wittkopf. 1993. A Point symmetry group of a differential equation which cannot be found using infinitesimal methods. In {\em Modern Group Analysis: Advanced Analytical and Computational Methods in Mathematical Physics}. Edited by N.H. Ibragimov, M. Torrisi and A. Valenti. 93--99. (Kluwer, Dordrecht). \bibitem{ReiWit93} Reid, G.J. and A. D. Wittkopf. 1993. The long guide to the Standard Form package. Programs and documentation available by anonymous ftp. \begin{rawhtml} [Anonymous ftp-address] . \end{rawhtml} \bibitem{RabRhe94} Rabier, P.J. and W.C. Rheinboldt. 1994. {\em A geometric treatment of implicit differential-algebraic equations}, Journal of Differential Equations, {\bf 109} 110-146. \bibitem{Riq10} Riquier, C. 1910. Les Syst\`{e}mes d'\'{E}quations aux D\'{e}riv\'{e}es Partielles. (Gauthier-Villars, Paris). \bibitem{Rit50} Ritt, J.F. 1950. {\em Differential Algebra}, Amer. Math. Soc. Colloq. Publns. {\bf 13} (A.M.S., New York). \bibitem{Ros59} Rosenfeld, A. 1959. {\em Specialisations in differential algebra}. Trans. Amer. Math. Soc. {\bf 90}, 394-407. \bibitem{Rus93} Rust, C. 1993. {\em On The Classification of Rankings of Partial Derivatives}, Preprint. \bibitem{RusRei97} Rust, C. and G.J. Reid. 1997. {\it Rankings of Partial Derivatives}, in Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, 9--16 (acm press, New York). \bibitem{Rus98} Rust, C. 1998. {\it Rankings of Derivatives for Elimination Algorithms and Formal Solvability of Analytic Partial Differential Equations}, Ph.D Thesis (Univ. of Chicago). \begin{rawhtml} [Retrieve PostScript] [Retrieve DVI] . \end{rawhtml} \bibitem{SchSeiCal92} Sch\"{u}, J., W.M. Seiler, and J. Calmet. 1992. {\em Algorithmic Methods for Lie Pseudogroups}, In {\em Modern Group Analysis: advanced analytical and computational methods in mathematical physics}. Ibragimov, N., Torrisi, M. and Valenti, A. eds. Kluwer, Dordrecht. \bibitem{Sch84} Schwarz, F. 1984. {\em The Riquier-Janet theory and its application to nonlinear evolution equations}, Physica {\bf D11} 243--251. \bibitem{Sch85} Schwarz, F. 1985. {\em Automatically determining symmetries of differential equations}, Computing. {\bf 34} 91--106. \bibitem{Sch92} Schwarz, F. 1992. {\em An Algorithm for Determining the Size of Symmetry Groups}, Computing {\bf 49} 95--115. \bibitem{Sch92b} Schwarz, F. 1992. {\em Reduction and completion algorithms for Partial Differential Equations}, In Proc. ISSAC '92. 49--56. (ACM Press, Berkeley). \bibitem{Sei56} Seidenberg, A. 1956. {\em An elimination theory for differential algebra}, University of California Publ. in Math. New Series {\bf 3}/2, 31-66. \bibitem{Sei94} Seiler, W.M. 1994. {\em Analysis and application of the formal theory of partial differential equations}, Ph.D. thesis, Lancaster University. \bibitem{ShePri92} Sherring, J. and G. Prince. 1992. {\em DIMSYM - Symmetry Determination and Linear Differential Equations Package},\, Preprint, Department of Mathematics\, (LaTrobe University, Bundoora, Australia). \bibitem{SeiVasRog94} Seiler, W. M., P. J. Vasiliou and C. Rogers. {\em Formal Analysis of the general Cauchy problem for the system: $u_t=u_{xx}$, $u_y=u_{xx}$}, Preprint. \bibitem{SinSte65} Singer, I.M. and Sternberg, S. 1965. {\em The infinite groups of Lie and Cartan. I.~The transitive groups}, J. d'Analyse Math., {\bf 15} 1--115. \bibitem{Spe69} Spencer, D. 1969. {\em Overdetermined Systems of Linear Differential Equations}, Bull. A.M.S. {\bf 75} 179--239. \bibitem{SurJan61} \v Surygin, V.A. and N.N. Janenko. 1961. {\em On the realization on electronic computing machines of algebraico-differential algorithms}, Problemy Kibernetika {\bf 6} 33--43 (in Russian). \bibitem{Tho29} Thomas, J.M. 1929. {\em Riquier's existence theorems}, Annals of Math. {\bf 30} 285--310. \bibitem{Tho31} Thomas, J. M. 1931. {\em Riquier's Existence Theorems}, Annals of Math. {\bf 35}, 306-311. \bibitem{Top89} Topunov, L. 1989. {\em Reducing systems of linear differential equations to a passive form}, Acta Appl. Math. {\bf 16} 191--206. \bibitem{Tre94} Tresse, A. 1894. {\em Sur les invariants diff\'{e}rentiels des groupes continus de transformations}, Acta Mathematica {\bf 18} 1--88. (English translation I. Lisle 1989, available from the author). \bibitem{Ves24} Vessiot, E. 1924. {\em Sur une th\'eorie nouvelle des probl\`emes g\'en\'eraux d'integration}, Bull. Soc. Math. Fr. {\bf 52} 336--395. \bibitem{Wei93} Weispfenning, V. 1993. {\em Differential-Term Orders}, In Proc. of ISAAC '93, (Kiev, ACM press). \bibitem{Wol87} Wolf, T. 1987. {\em A package for the analytic investigation and exact solutions of differential equations},\, in: Proc. EUROCAL '87, Leipzig, GDR, Ed.: J.H. Davenport,\, Lecture Notes in Computer Science {\bf 378}\, (Springer Verlag, Berlin, 1989) 479--491. \end{thebibliography} \end{document}