| Both sides previous revision Previous revision Next revision | Previous revision |
| reference:permutations [2016/03/14 14:27] – [Introduction of a permutation] gawrilow | user_guide:extend:permutations [2019/05/07 13:37] (current) – [The problem] lkastner |
|---|
| |
| ===== 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. |
| 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. |
| |
| ==== Creation of permuted subobjects ==== | ==== 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. | 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. |
| |
| 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. |