Opened 19 months ago
Closed 17 months ago
#28506 closed defect (fixed)
Direct sum of polyhedron is broken, so is minkowski difference and face truncation
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  geometry  Keywords:  polytopes 
Cc:  ghLaisRast, ghkliem  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  6756d8a (Commits, GitHub, GitLab)  Commit:  6756d8a870674020479fcceef4a8d450fb87ea4f 
Dependencies:  Stopgaps: 
Description (last modified by )
The following returns a TypeError
:
sage: s2 = polytopes.simplex(2) sage: s3 = polytopes.simplex(3) sage: t = s2.direct_sum(s3)
HPolyhedra might have nonintegral vertices and it is hard to tell from the HRepresentation, whether this this is the case.
We fix direct_sum
, minkowski_difference
and face_truncation
to try the quotient ring, if the given base ring does not work.
Change History (19)
comment:1 Changed 19 months ago by
comment:2 Changed 19 months ago by
minkowski_difference
fails for the same reason. This fails, as coercing base rings may not suffice:
sage: Q = Polyhedron([[1,0],[0,1]]) sage: S = Polyhedron([[0,0],[1,2]]) sage: S.minkowski_difference(Q)
Same for face_truncation
(also there is no example of linear coefficients in the docstring):
sage: P = polytopes.permutahedron(3) sage: P.face_truncation(P.faces(0)[0], linear_coefficients=[0,1,2], cut_frac=1)
comment:3 Changed 19 months ago by
 Branch set to public/28506
 Commit set to e86ea8b2bbd1fdd017aa22a9318d3f08c3c3cfe6
 Description modified (diff)
 Status changed from new to needs_review
 Summary changed from Direct sum of polyhedron is broken to Direct sum of polyhedron is broken, so is minkowski difference and face truncation
I did both approaches. The approach that always takes the fraction is pushed into public/28506bis
.
I guess there are pros and cons of both methods. I think most important cons are:
try ... except
might take more much more time (I assume it can theoretically compute almost everything)try ... except
is a bad approach, if there was ever a thing as a lazy polyhedron (but then again, its a bad idea to set up a lazy Polyhedron inZZ
from inequalities and don't check, whether this works) always taking fraction field changes the behavior of the methods (and it looks awful for Minkowski decomposition)
New commits:
fa1a517  added doctests that 28506 is fixed

e86ea8b  fixed 28506 by trying fraction field at failure

comment:4 Changed 19 months ago by
Btw, the constructor sets up all HPolyhedra with base ring as field unless one specifies a specific base ring.
Actually, I think this is the better approach, as construction should be done with a parent, for which they are welldefined, e.g.:
 intersection of Polyhedra in
ZZ^2
are only welldefined inQQ^2
, it's strange if some constructions have parentZZ^2
, while others have parentQQ^2
face_truncation
for Polyhedra overZZ
is only welldefined if we lift them up toQQ
comment:5 followup: ↓ 6 Changed 19 months ago by
One comment:
The tests should actually return something, so I would remove t =
and let the output get printed.
I am still a bit puzzled as to why it did not work for direct sum. What was going on there?
comment:6 in reply to: ↑ 5 ; followup: ↓ 8 Changed 19 months ago by
Replying to jipilab:
One comment:
The tests should actually return something, so I would remove
t =
and let the output get printed.
Ok. Will do it.
I am still a bit puzzled as to why it did not work for direct sum. What was going on there?
sage: s2 = polytopes.simplex(2) sage: s2.base_ring() Integer Ring sage: s = polytopes.simplex(2) sage: s.base_ring() Integer Ring sage: s = s.change_ring(QQ) sage: t = s.direct_sum(s) sage: t.vertices() (A vertex at (0, 0, 1, 0, 0, 0), A vertex at (0, 1, 0, 0, 0, 0), A vertex at (1, 0, 0, 0, 0, 0), A vertex at (1/3, 1/3, 1/3, 1/3, 1/3, 2/3), A vertex at (1/3, 1/3, 1/3, 1/3, 2/3, 1/3), A vertex at (1/3, 1/3, 1/3, 2/3, 1/3, 1/3))
Does this answer your question? As mentioned, direct sum (as well as intersection, minkowski difference and face truncation) are only defined for polytopes/polyhedra over a field.
In the same way, that sage: 6/2
returns a rational, I think those operations should return a polytope with base ring constructed by first coercing and then taking the fraction field.
comment:7 Changed 19 months ago by
 Branch changed from public/28506 to public/28506bis
 Commit changed from e86ea8b2bbd1fdd017aa22a9318d3f08c3c3cfe6 to 20ad51f952b05e8ec8888e54501365f72ca527a4
As mentioned. I think this approach is actually more suitable and at some point, we should change intersection
accordingly.
New commits:
20ad51f  fixed 28506 by always taking fraction field

comment:8 in reply to: ↑ 6 ; followup: ↓ 10 Changed 19 months ago by
Replying to ghkliem:
Replying to jipilab:
One comment:
The tests should actually return something, so I would remove
t =
and let the output get printed.Ok. Will do it.
I am still a bit puzzled as to why it did not work for direct sum. What was going on there?
sage: s2 = polytopes.simplex(2) sage: s2.base_ring() Integer Ring sage: s = polytopes.simplex(2) sage: s.base_ring() Integer Ring sage: s = s.change_ring(QQ) sage: t = s.direct_sum(s) sage: t.vertices() (A vertex at (0, 0, 1, 0, 0, 0), A vertex at (0, 1, 0, 0, 0, 0), A vertex at (1, 0, 0, 0, 0, 0), A vertex at (1/3, 1/3, 1/3, 1/3, 1/3, 2/3), A vertex at (1/3, 1/3, 1/3, 1/3, 2/3, 1/3), A vertex at (1/3, 1/3, 1/3, 2/3, 1/3, 1/3))Does this answer your question? As mentioned, direct sum (as well as intersection, minkowski difference and face truncation) are only defined for polytopes/polyhedra over a field.
Yes, this examples clarifies it. It should probably go right among the first examples to illustrate the construction.
I was extremely confused, but now it makes sense. The problem is when we translate one of them to have center be the origin...
In the same way, that
sage: 6/2
returns a rational, I think those operations should return a polytope with base ring constructed by first coercing and then taking the fraction field.
Yes, sounds reasonable.
comment:9 Changed 19 months ago by
 Commit changed from 20ad51f952b05e8ec8888e54501365f72ca527a4 to ce30313f34389112c87c250181e16c3c9f211917
Branch pushed to git repo; I updated commit sha1. New commits:
ce30313  added output to doctest

comment:10 in reply to: ↑ 8 ; followup: ↓ 12 Changed 19 months ago by
Replying to jipilab:
Replying to ghkliem:
Replying to jipilab:
One comment:
The tests should actually return something, so I would remove
t =
and let the output get printed.Ok. Will do it.
I am still a bit puzzled as to why it did not work for direct sum. What was going on there?
sage: s2 = polytopes.simplex(2) sage: s2.base_ring() Integer Ring sage: s = polytopes.simplex(2) sage: s.base_ring() Integer Ring sage: s = s.change_ring(QQ) sage: t = s.direct_sum(s) sage: t.vertices() (A vertex at (0, 0, 1, 0, 0, 0), A vertex at (0, 1, 0, 0, 0, 0), A vertex at (1, 0, 0, 0, 0, 0), A vertex at (1/3, 1/3, 1/3, 1/3, 1/3, 2/3), A vertex at (1/3, 1/3, 1/3, 1/3, 2/3, 1/3), A vertex at (1/3, 1/3, 1/3, 2/3, 1/3, 1/3))Does this answer your question? As mentioned, direct sum (as well as intersection, minkowski difference and face truncation) are only defined for polytopes/polyhedra over a field.
Yes, this examples clarifies it. It should probably go right among the first examples to illustrate the construction.
I could of course do it. But doesn't the existing example already illustrate this?
I was extremely confused, but now it makes sense. The problem is when we translate one of them to have center be the origin...
In the same way, that
sage: 6/2
returns a rational, I think those operations should return a polytope with base ring constructed by first coercing and then taking the fraction field.Yes, sounds reasonable.
comment:11 Changed 19 months ago by
 Commit changed from ce30313f34389112c87c250181e16c3c9f211917 to 7080349f1d4255d8211657689181cc13b9096977
Branch pushed to git repo; I updated commit sha1. New commits:
7080349  fixed minkowski decomposition

comment:12 in reply to: ↑ 10 Changed 19 months ago by
Replying to ghkliem:
I could of course do it. But doesn't the existing example already illustrate this?
True.
comment:13 Changed 18 months ago by
 Milestone changed from sagepending to sage9.0
 Reviewers set to JeanPhilippe Labbé
The "some tests::" might be superfluous. I would remove it.
comment:14 Changed 18 months ago by
 Commit changed from 7080349f1d4255d8211657689181cc13b9096977 to b1c81876e5c2a7b765df8984320ca1d3514764b6
Branch pushed to git repo; I updated commit sha1. New commits:
b1c8187  small changes in documentation

comment:15 Changed 18 months ago by
 Status changed from needs_review to needs_work
Some tests are failing in the thematic tutorial. See patchbots.
comment:16 Changed 18 months ago by
 Branch changed from public/28506bis to public/28506reb2
 Commit changed from b1c81876e5c2a7b765df8984320ca1d3514764b6 to 47514e7d31f9d22227ea16c67b18fb4330f134f4
 Status changed from needs_work to needs_review
comment:17 Changed 18 months ago by
 Commit changed from 47514e7d31f9d22227ea16c67b18fb4330f134f4 to 6756d8a870674020479fcceef4a8d450fb87ea4f
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6756d8a  fixed trac 28506

comment:19 Changed 17 months ago by
 Branch changed from public/28506reb2 to 6756d8a870674020479fcceef4a8d450fb87ea4f
 Resolution set to fixed
 Status changed from positive_review to closed
I'll fix it. Should be fast.
As far as I know, it's difficult to determine, whether this operation can be done with ring
ZZ
. So there are basically two options:intersection
handles it)What do you think is better?