Permutations of "Big" Objects [polymake wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Permutations of "Big" Objects ======
**Warning to begin with:** this page does not deal with permutations as elements of groups nor with symmetries of polytopes; there is a whole application "group" about it.  This essay is devoted to a rather technical problem which an author of every application should be aware of.

===== The problem =====
Many properties of "big" objects do not have a unique representation.  For example, a polyhedron can be given by a non-redundant system of inequalities and equations, called FACETS and AFFINE_HULL in application "polytope"; both are encoded as matrices, each row containing a normal vector to the corresponding hyperplane.  If you permute the order of FACET inequalities, or exchange the set of basis vectors of AFFINE_HULL, you will still obtain the description of the same polyhedron, but from the pure technical point of view it would be a different object.  As such, the multitude of representations should not constitute a serious problem as long as the functions, say, comparing two polyhedrons for equality, can deal with it algorithmically.

The situation becomes more intricate, however, when further properties depend on the exact values of these non-unique ones.  For example, the order of rows of the FACETS matrix implicitly assigns an identity to each facet, knowing which is then crucial for correct interpretation of many other properties referring to FACETS, like DUAL_GRAPH or HASSE_DIAGRAM.  Now, when two production rules would create properties referring to FACETS and assume different orders of them, we'd end up with an inconsistent description of a polyhedron.

Polymake has a mechanism precluding this danger.  Each transformation of the "big" object description which would lead to the same object (or speaking more generally, preserving the equivalence class of objects represented by the original one), should be explicitly declared as a //permutation// as soon as more than one property is effected by this transformation //and// there are production rules creating such properties "from scratch", that is, without caring about existence of other related properties in the object.  

Note that the name //permutation// is chosen just due to the observation that most transformations of such kind can be easily expressed as permutations of some items being part of the object description, like vertices, rays, facets, or graph nodes.  The example with AFFINE_HULL shows, however, that the transformation can also involve other operations (even if this concrete example does not occur in the current application "polytope").  Please also note the fundamental difference between, on the one hand, a mere permutation of items like FACETS or VERTICES which does not lead to any new insights about the nature of the object and, on the other hand, different kinds of triangulations of the same polyhedron which might have completely different mathematical properties.  In the latter case the application designer should model it as a multiple subobject, allowing for concurrent existence of several different instances.

===== Describing a permutation =====
The description of a permutation and its influence on the object properties is distributed over the rulebase, possibly scattered over several rule files.  It consists of the following parts:

==== Introduction of a permutation ====
Each permutation is introduced by a [[rulefiles:permutations|declaration]] in the "big" object definition scope.  From the technical point of view, it is a subobject property of some basic type automatically augmented by the actual type of the parent object.  A derived "big" object type inherits all permutations from its base type much like any other property, but the specialty of permutations is that their final type is automatically adjusted by augmentation by the corresponding parent object.

  object Cone {
    permutation FacetPerm : PermBase;
  }

Permutations can also be augmented explicitly, e.g. in order to introduce additional properties supporting more efficient computations of permutations of derived or specialized types, e.g.

  object Polytope<Specialized> {
    # inherits the basic properties of Cone::FacetPerm
    permutation FacetPerm {
      property HELPER : Vector<Specialized>;
    }
  }

==== Computing the transformation ====
The permutation properties should be computable by comparison of some property values in the parent object and in the transformed subobject.  These computations must be cast into production rules.  As there might be more than one way how to compute the transformation, the corresponding production rules may have different weights, preconditions, etc.:
  rule FacetPerm.PERMUTATION : FACETS, FacetPerm.FACETS {
    # canonicalize and compare two matrices row-wise: low complexity
  }
  weight 2.10
  rule FacetPerm.PERMUTATION : VERTICES_IN_FACETS, FacetPerm.VERTICES_IN_FACETS {
    # solve the isomorphism problem for bipartite graphs: high complexity
  }
  weight 4.10

==== Reconstructing properties sensitive to permutations ====
For any property whose concrete physical representation depends on a permutation, there should be at least one production rule picking this property in the transformed subobject (and, surely, some other properties of it), and computing the same property in the parent object.  The mere existence of such a rule signals to polymake that the property is sensitive to the permutation.  The property may also belong to a nested subobject of the "big" object being transformed.  For example, the following rule transforms the facet-vertex incidence matrix of a polyhedron according to the known permutation of its facets:
  rule VERTICES_IN_FACETS : FacetPerm.VERTICES_IN_FACETS, FacetPerm.PERMUTATION { ... }
The presence of this rule tells polymake that the concrete value of VERTICES_IN_FACETS depends on the chosen order of the facets, thus this property is sensitive to FacetPerm.

Sometimes the value of the property can't be easily transformed for a given permutation, so that it is easier to recompute it from scratch using normal production rules.  Even in this case polymake must be told about sensitivity; to this end, a pseudo-rule without body and labeled with a special word ''nonexistent'' must be written.

==== Propagating the permutation into subobjects ====
A transformation of an object may lead to related transformations in its subobjects.  For example, a permutation of the order of vertices of a polyhedron causes corresponding permutations of the nodes in the vertex graph and of the vertices in all triangulations.  The permutation of the parent must, so to speak, be propagated into subobjects.  These connections are to be expressed by production rules computing some properties of a subobject permutation from the parent's permutation:
  rule DUAL_GRAPH.NodePerm.PERMUTATION : FacetPerm.PERMUTATION { ... }
  rule TRIANGULATION.VertexPerm.PERMUTATION : VertexPerm.PERMUTATION { ... }
Often, the "computation" is a trivial copy of an array of indices, in which case a [[rules#shortcuts|shortcut rule]] may be used.

Connecting two permutations with such a rule automatically makes all properties sensitive to the permutation of the subobject also being sensitive to the permutation of the parent object.

==== Creating permuted subobjects ====
All the declarations and rules described above define the nature of the permutation and its effect on the object properties, but does not explain when a permuted subobject comes into existence in the first place.  Permuted subobjects are created automatically by polymake in the course of execution of a rule chain, when a production rule marked as [[rules#permutations|incurring this permutation]] is applied to an object already containing at least one property sensitive to this permutation or to a permutation propagated from this one into its subobjects.  Then all target properties being sensitive to this permutation are moved into the freshly created permuted subobject immediately after the production rule completion.  Later in the rule chain, additional production rules (of the kinds described above) will calculate the necessary transformation properties and eventually transfer the created properties back to the parent object.  The permuted subobject will finally be destroyed after the completion of the entire rule chain.

For example, the following rule (computing a convex hull of a polyhedron):
  rule FACETS, AFFINE_HULL, VERTICES_IN_FACETS, TRIANGULATION.FACETS, DUAL_GRAPH.ADJACENCY : VERTICES { ... }
  incurs FacetPerm;
would create a subobject hierarchy consisting of FacetPerm.FACETS, FacetPerm.VERTICES_IN_FACETS, TRIANGULATION.FacetPerm.FACETS, DUAL_GRAPH.NodePerm.ADJACENCY, if the object would accidentally already contain any property sensitive to FacetPerm, e.g. FACETS.

If the rule chain contains several production rules incurring a permutation, each one gives raise to its own instance of a permutation subobject which do not interfere with each other.

===== Final Remarks =====
Sometimes an application can do without a permutation as long as it is used autonomously, but eventually needs it when used in combination with others.  For example, the vertices of a SimplicialComplex (dealt with in the application "topaz") never appear on the stage on their own but rather as elements of the faces the complex consists of.  Thus, this application would not need to take care of vertex permutations unless other applications like "polytope" or "fan" define triangulations and other properties sensitive to vertex permutations as subobjects of type SimplicialComplex.  As one can rarely predict all future use cases of a new application, it is better to invest a bit more time in the initial design phase and take care of most probable permutations in advance.  At least one should express the sensitivity of properties to the permutations by means of non-existing rules, so as to stay on the safe side if some day the permutation will be propagated into the object from some future parent.

When deciding how many and what kind of rules to implement for a permutation, one should keep in mind the following "peculiarity" of the rule scheduler: even though the type of a permuted subobject is augmented by its parent type, it //does not// inherit the normal production rules.  The only rules considered by the scheduler for the sequel of a production rule incurring a permutation are those calculating the local properties and restoring the properties in the parent object.  This is not an implementation defect, but a deliberate precautionary measure limiting the combinatorial explosion of all possible rule chains to consider.  Thus, if any of the aforementioned rules need an additional input being invariant to the permutation, they must take it from the parent object, because invariant properties never appear in the permuted subobject.