#10148 closed enhancement (fixed)
Automorphism group of a Polyhedron
Reported by: | vbraun | Owned by: | mhampton |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.1 |
Component: | geometry | Keywords: | |
Cc: | novoselt | Merged in: | sage-4.6.1.alpha0 |
Authors: | Volker Braun | Reviewers: | Andrey Novoseltsev |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The attached patch allows one to compute the automorphism group of a Polyhedron
.
Attachments (1)
Change History (16)
comment:1 Changed 12 years ago by
- Status changed from new to needs_review
comment:2 Changed 12 years ago by
- Cc novoselt added
comment:3 Changed 12 years ago by
- Status changed from needs_review to needs_work
comment:4 Changed 12 years ago by
- Reviewers set to Andrey Novoseltsev
Thanks for catching the translation bug. The restricted automorphism group should be D_6
(dihedral group with 6 elements) in all cases.
I've renamed the method to restricted_automorphism_group()
.
I don't think that you can't get rid of lines; The Polyhedron class makes no guarantees that the vertex and ray generators are in a common hypersurface of codimension = number of lines. So the restricted automorphism group will always depend on the presentation of the polyhedron. Once you embrace this fact there is no particular reason to disallow permutations of line generators...
comment:5 Changed 12 years ago by
As a follow up to my comments, how about moving _affine_coordinates
inside automorphism group
and making it discard line generators in computing pivots. This way linear subspaces will not affect the computed group, which is good, in my opinion. The drawback is that translation from permutations to generators will be a bit more complicated, but the function can take care of it and return the group that still acts on all generators, just keeps line ones fixes.
If I am right and the algorithm will compute GL(R,n) symmetries in the compact case, how about keeping the name automorphism_group
but issuing a warning like "you have requested the restricted automorphism group of a non-compact polyhedron. Please read the documentation to make sure that it is the group that you want." for non-compact ones?
Also, as I understand it, it is possible to add any extra stuff to graph labels if one wants to, as you have done to prevent mixing ray and vertex generators. How about adding the possibility to add integral lengths (lattice_polytope.integral_length
computes it saving you a couple lines ;-)) to these labels so that the computed group is the group of symmetries with respect to GL(Z, n)? Another option can be adding the square of the "real distance" to compute, I guess, O(n) symmetries.
comment:6 Changed 12 years ago by
You are right, discard the first paragraph above, but the second one becomes even more relevant then ;-)
comment:7 Changed 12 years ago by
"Translations do change the restricted automorphism group." I think you missed NOT.
comment:8 Changed 12 years ago by
- Status changed from needs_work to needs_review
Yes, the "not" is important :-)
I guess you want the linear automorphism group as automorphism_group()
? There is also the combinatorial automorphism group... Note that the restricted automorphism group equals the linear automorphism group in the case of a full-dimensional compact polyhedron.
I think the (linear) automorphism_group()
should return the group elements as Euclidean group elements. But there is no class for that, and tuples (A,b)
isn't that intuitive. I don't have time to implement it right now, maybe later. Need to figure out what to do with the continuous group generators, too...
If your polytope is a lattice polytope then the restricted automorphism group is automatically a subgroup of the lattice Euclidean group GL(d,Z) |x Z^d
.
comment:9 Changed 12 years ago by
- Status changed from needs_review to needs_work
First of all, let me correct myself - when I was talking about GL-symmetries, of course I meant affine-linear ones - they just happen to be the same for reflexive polytopes and I forgot about general situation.
I am more interested in the linear automorphism group and even more in the lattice preserving one, rather than in the combinatorial one. I think the abundance of automorphism groups indicates that maybe we should never have a method called just automorphism_group
, but always indicate its kind, as it is done in the new patch.
The current implementation does not preserve the lattice - the example that I have given above is the polytope of WP(1,1,2) and one of the edges has length 2 while others only 1. So there is only one lattice-preserving symmetry. (But that's OK for this ticket.)
Previously raised issues were addressed, but I have some new comments :-)
- "Note that there are no translations possible since
Q
contains only a single vertex." is a bit misleading. "Separate" translations are possible iff there is a non-trivial linear subspace. In this case you probably meant that there are no "translation components" attached to matrices, since there is only a single vertex. I think this either should be explained in more detail, or not mentioned at all. - I don't understand how the floating point part works. I am not at all an expert on such cases, but I don't understand how calling a function returning
x == 0
is any different from direct comparison with 0, which should not be done for floating point numbers anyway. How can it ever returnTrue
for anything but exactly zero? It seems to me that you should be comparingx-c
with the absolute value ofx
andc
and if the ratio is too small, declare it to be zero. Probably some care should be taken in the case whenx
orc
is actually zero. Fixing some absolute threshold in advance forx-c
will lead to incorrect work with "small" polyhedra, but maybe some rough estimate for the diameter can be used. E.g. it is relatively cheap to compute the bounding box of the polyhedra generators and then declare its size divided by 10^{6} or so to be zero. Or one can try to be more clever and choose this tolerance based on the actual "edge colors" before rounding. The current version seems to be too fragile to me. - I think you should treat vertices and rays/lines differently when constructing
v_list
, adding 1 to vertices (which fixed translation issues above) and 0 to others. Otherwisesage: p = Polyhedron(vertices=[(1,0), (1,1)], rays=[(1,0)]) sage: p.restricted_automorphism_group().order() 1
while it should be 2, I think.
comment:10 Changed 12 years ago by
- I meant that in the concrete case of the quadrant there are no translations. I'll try to re-word it.
- The
_is_zero(x)
method isabs(x)<1e-7
if thePolyhedron.field()
isRDF
. So that implements the fuzzy zero. Its definitely simple-minded, but then thats whatcdd
uses internally:sage: Polyhedron(vertices=[(0,), (1e-8,)], field=RDF) A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex.
- Thanks, forgot about that %-)
comment:11 Changed 12 years ago by
Ah, now that makes sense! I guess I just have an issue with _is_zero
because I looked at the source code of it for some polyhedron (which happened to be exact) using ??
and saw x == 0
without paying too much attention to the details. The Polyhedron
class itself does not have such a method at all. Is really speed-crucial to set it to a lambda-expression instead of having an honest method with if-check for the type of the field each time? (For the purposes of this ticket 2 is resolved.)
comment:12 Changed 12 years ago by
- Status changed from needs_work to needs_review
I'm planning to make _is_zero
, _is_nonneg
and _is_positive
into overloaded methods when I split up Polyhedron
into different backends. But first I wanted to commit the outstanding patches I have.
I'm not sure that labeling the edges with the number of lattice points restricts to the lattice Euclidean group automatically. Can't you still map a minimal 2-d triangle, say, to one with an interior point (but no lattice point on the edges)? Thats of course not a counterexample, but its not clear to me that that might not happen on faces of higher-dimensional polyhedra...
Updated patch for 1. and 3. is attached. I've also added a combinatorial_automorphism_group()
method to compare with.
comment:13 Changed 12 years ago by
- Milestone changed from sage-feature to sage-4.6.1
- Status changed from needs_review to positive_review
You are right, it is not that easy to make this algorithm work for lattice-preserving automorphisms. Let's save this for later ;-)
The latest patch looks and works fine, positive review!
comment:14 Changed 12 years ago by
- Merged in set to sage-4.6.1.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:15 Changed 6 years ago by
"Euclidean group" should be "affine group", see #20063.
_affine_coordinates
does not check if the input is valid (i.e. you can pass a point which is not in the affine space), but it is worth noting this feature in its documentation.automorphism_group
docstring.assert(False)
looks really weird, even though I understand what does it mean. Personally, I'd rather not have that line at all.automorphism_group
is justified. It should be either more descriptive or take a mandatory parameter specifying its type, likeautomorphism_group("restricted")
withautomorphism_group()
raising an exception. I think that at least for bounded polyhedraautomorphism_group
should mean GL(R,n)-symmetries.Examples:
I want to get the same number in each case. Personally, I like 2 as the number of GL(Z,2)-symmetries, but as I understand the referenced paper, it should be 6, the number of GL(R,2)-symmetries.