#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: sage-9.0
Component: geometry Keywords: polytopes
Cc: gh-LaisRast, gh-kliem Merged in:
Authors: Jonathan Kliem Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 6756d8a (Commits, GitHub, GitLab) Commit: 6756d8a870674020479fcceef4a8d450fb87ea4f
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-kliem)

The following returns a TypeError:

sage: s2 = polytopes.simplex(2)
sage: s3 = polytopes.simplex(3)
sage: t = s2.direct_sum(s3)

H-Polyhedra might have non-integral vertices and it is hard to tell from the H-Representation, 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 gh-kliem

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:

  • try the operation with coerced base rings and go to quotient field, if it fails (this is how intersection handles it)
  • just go to field in all cases.

What do you think is better?

comment:2 Changed 19 months ago by gh-kliem

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 gh-kliem

  • Authors set to Jonathan Kliem
  • 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/28506-bis.

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 in ZZ 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:

fa1a517added doctests that 28506 is fixed
e86ea8bfixed 28506 by trying fraction field at failure

comment:4 Changed 19 months ago by gh-kliem

Btw, the constructor sets up all H-Polyhedra 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 well-defined, e.g.:

  • intersection of Polyhedra in ZZ^2 are only well-defined in QQ^2, it's strange if some constructions have parent ZZ^2, while others have parent QQ^2
  • face_truncation for Polyhedra over ZZ is only well-defined if we lift them up to QQ

comment:5 follow-up: Changed 19 months ago by jipilab

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 ; follow-up: Changed 19 months ago by gh-kliem

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 gh-kliem

  • Branch changed from public/28506 to public/28506-bis
  • 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:

20ad51ffixed 28506 by always taking fraction field

comment:8 in reply to: ↑ 6 ; follow-up: Changed 19 months ago by jipilab

Replying to gh-kliem:

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 git

  • Commit changed from 20ad51f952b05e8ec8888e54501365f72ca527a4 to ce30313f34389112c87c250181e16c3c9f211917

Branch pushed to git repo; I updated commit sha1. New commits:

ce30313added output to doctest

comment:10 in reply to: ↑ 8 ; follow-up: Changed 19 months ago by gh-kliem

Replying to jipilab:

Replying to gh-kliem:

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 git

  • Commit changed from ce30313f34389112c87c250181e16c3c9f211917 to 7080349f1d4255d8211657689181cc13b9096977

Branch pushed to git repo; I updated commit sha1. New commits:

7080349fixed minkowski decomposition

comment:12 in reply to: ↑ 10 Changed 19 months ago by jipilab

Replying to gh-kliem:

I could of course do it. But doesn't the existing example already illustrate this?

True.

comment:13 Changed 18 months ago by jipilab

  • Milestone changed from sage-pending to sage-9.0
  • Reviewers set to Jean-Philippe Labbé

The "some tests::" might be superfluous. I would remove it.

comment:14 Changed 18 months ago by git

  • Commit changed from 7080349f1d4255d8211657689181cc13b9096977 to b1c81876e5c2a7b765df8984320ca1d3514764b6

Branch pushed to git repo; I updated commit sha1. New commits:

b1c8187small changes in documentation

comment:15 Changed 18 months ago by jipilab

  • 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 gh-kliem

  • Branch changed from public/28506-bis to public/28506-reb2
  • Commit changed from b1c81876e5c2a7b765df8984320ca1d3514764b6 to 47514e7d31f9d22227ea16c67b18fb4330f134f4
  • Status changed from needs_work to needs_review

New commits:

fc62aa6fixed trac 28506
fa4ddc1fixed failing doctest in documentation
47514e7Fixed trac 28506

comment:17 Changed 18 months ago by git

  • Commit changed from 47514e7d31f9d22227ea16c67b18fb4330f134f4 to 6756d8a870674020479fcceef4a8d450fb87ea4f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

6756d8afixed trac 28506

comment:18 Changed 18 months ago by jipilab

  • Status changed from needs_review to positive_review

LGTM

comment:19 Changed 17 months ago by vbraun

  • Branch changed from public/28506-reb2 to 6756d8a870674020479fcceef4a8d450fb87ea4f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.