A symmetry of a 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 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 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 PDEs, 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 [56,58] 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 PDEs. 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 [78] 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 [62] 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 [62] was not able to calculate structure of infinite Lie pseudogroups of symmetries of PDEs. 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).