user_guide:extend:permutations

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
reference:permutations [2012/04/01 23:59] – [Permutations of Big Objects] gawrilowuser_guide:extend:permutations [2019/05/07 13:37] (current) – [The problem] lkastner
Line 3: Line 3:
  
 ===== The problem ===== ===== The problem =====
-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.+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. 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.
Line 15: Line 15:
  
 ==== Introduction of a permutation ==== ==== 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 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: +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. 
-  declare permutation FacetPerm + 
-    property PERMUTATION Array<Int>;+  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 ==== ==== Computing the transformation ====
-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.: +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 {+  rule FacetPerm.PERMUTATION : FACETS, FacetPerm.FACETS {
     # canonicalize and compare two matrices row-wise: low complexity     # canonicalize and compare two matrices row-wise: low complexity
   }   }
   weight 2.10   weight 2.10
-  rule FacetPERM.PERMUTATION : VERTICES_IN_FACETS, FacetPerm.VERTICES_IN_FACETS {+  rule FacetPerm.PERMUTATION : VERTICES_IN_FACETS, FacetPerm.VERTICES_IN_FACETS {
     # solve the isomorphism problem for bipartite graphs: high complexity     # solve the isomorphism problem for bipartite graphs: high complexity
   }   }
   weight 4.10   weight 4.10
  
-==== Determining properties sensitive to the permutation ==== +==== Reconstructing properties sensitive to permutations ==== 
-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:+For any property whose concrete physical representation depends on 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 { ... }   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. 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.
Line 45: Line 56:
 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. 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.
  
-==== Triggering the permutation ==== +==== 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 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 [[rules#permutations|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.+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): 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 { ... }   rule FACETS, AFFINE_HULL, VERTICES_IN_FACETS, TRIANGULATION.FACETS, DUAL_GRAPH.ADJACENCY : VERTICES { ... }
-  permutation FacetPerm; +  incurs 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.+would create a subobject hierarchy consisting of FacetPerm.FACETS, FacetPerm.VERTICES_IN_FACETS, TRIANGULATION.FacetPerm.FACETS, DUAL_GRAPH.NodePerm.ADJACENCYif 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.+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 ===== ===== 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. 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.+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.
  • user_guide/extend/permutations.1333324756.txt.gz
  • Last modified: 2014/01/03 15:45
  • (external edit)