user_guide:extend:permutations

This is an old revision of the document!


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 special application “group” devoted to them. This essay is devoted to a rather technical problem which an author of every application should be aware of.

Many properties of “big” objects does 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.

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:

Each permutation is introduced by a declaration in the “big” object definition scope. From the technical point of view, it is a subobject property of a type equal to the type of the parent object with local extensions. A derived object type inherits all permutations from its ancestor much like any other property, but the specialty of permutations is that their type is automatically adjusted to that of the parent object. The local subobject definition scope should introduce properties encoding the transformation, for example, an array of indices encoding the permutation of the order of facets:

declare permutation FacetPerm {
  property PERMUTATION : Array<Int>;
}

The locally introduced properties should be computable from a 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

For each property whose concrete physical representation depends on the 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 some 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.

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 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.

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 permutation subobject comes into existence in the first place. Permutation subobjects are created automatically by polymake in the course of execution of a rule chain, when a production rule marked as triggering this permutation is executed at the moment as the object (or one of its subobjects) already contains at least one property sensitive to this permutation or (in the case of a subobject) to a permutation propagated from this one. Then all target properties being sensitive to this permutation are moved into the freshly created permutation subobject (or its subobjects) immediately after the termination of the production rule. 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 permutation subobject will be finally 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 { ... }
permutation FacetPerm;

would create a subobject hierarchy attached to FacetPerm consisting of FACETS, VERTICES_IN_FACETS, TRIANGULATION.FACETS, DUAL_GRAPH.ADJACENCY if the object would accidentally already contain any property sensitive to FacetPerm, e.g. FACETS.

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

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 permutation subobject is of a locally extended type derived from its parent, it does not inherit the normal production rules. The only rules considered by the scheduler for the sequel of a production rule triggering a permutation are those calculating the local properties and restoring the properties in the parent object. This is not an implementation defect, but a 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 permutation subobject.

  • user_guide/extend/permutations.1333324701.txt.gz
  • Last modified: 2014/01/03 15:45
  • (external edit)