Opened 5 years ago
Closed 5 years ago
#22558 closed defect (fixed)
.volume() of polyhedron does not handle unbounded polyhedron properly
Reported by: | jipilab | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.6 |
Component: | geometry | Keywords: | days84, geometry, volume, days88 |
Cc: | chapoton, vdelecroix, mkoeppe, moritz, jipilab | Merged in: | |
Authors: | Moritz Firsching | Reviewers: | Jean-Philippe Labbé, Franco Saliola |
Report Upstream: | N/A | Work issues: | |
Branch: | 3e0ada5 (Commits, GitHub, GitLab) | Commit: | 3e0ada5cae3ce4e136783784ecd6eb0cc574b9cf |
Dependencies: | #16045 | Stopgaps: |
Description
Currently, the method .volume()
of the polyhedron class (see .volume()) does not handle unbounded polyhedron internally and lets .triangulate()
return an error:
sage: P = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]]) sage: P.volume() Traceback (most recent call last): ... in triangulate(self, engine, connected, fine, regular, star) ... NotImplementedError: I can only triangulate compact polytopes.
One possibility would be to return infinity oo
in this case.
Change History (19)
comment:1 follow-up: ↓ 2 Changed 5 years ago by
comment:2 in reply to: ↑ 1 Changed 5 years ago by
Or zero depending on whether it is full-dimensional or not?
This is related to #16045, the user may want a different output in this case: the volume in the euclidean sense, or the "area" relative to the affine space, or even relative to the lattice index...
comment:3 Changed 5 years ago by
- Branch set to u/jipilab/22558
comment:4 Changed 5 years ago by
- Commit set to 0429a92cb38cc1a5aedf76eac58fba6d04f959e2
- Status changed from new to needs_review
New commits:
0429a92 | Added infinite volume
|
comment:5 Changed 5 years ago by
- Status changed from needs_review to needs_info
What should be the expected behavior for non-compact non-fulldimensional polyhedra?
From reading #16045 it seems that currently engine='lrs'
provides the volume in the affine hull while auto
provides the volume in the ambient space. To make your new function agree with this, I would expect the following output:
sage: Q = Polyhedron(ieqs=[[0, 1, 0], [0, -1, 0], [0, 0, 1]]); Q A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray sage: Q.volume() 0 sage: Q.volume(engine='lrs') +Infinity
Your version give +Infinity
in both cases.
I added the changes necessary for this, feel free to reset to your commit, if you don't like it. Perhaps it would be best to fix #16045 first.
comment:6 Changed 5 years ago by
- Branch changed from u/jipilab/22558 to u/moritz/22558
comment:7 Changed 5 years ago by
- Commit changed from 0429a92cb38cc1a5aedf76eac58fba6d04f959e2 to 3269ed27a9e46658dcd572f23e6e46a1703323eb
- Dependencies set to #16045
comment:8 Changed 5 years ago by
- Keywords days88 added
comment:9 Changed 5 years ago by
- Commit changed from 3269ed27a9e46658dcd572f23e6e46a1703323eb to 166f0f779d2827e3d64f82f5d9a467d51f52fab7
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b602072 | add measure option
|
09fb035 | using new affine_hull function to provide induced measure
|
5b68b13 | added one forgotten line in a doctest
|
5f452f5 | doctest for 'induced_rational'
|
b7b10da | small improvements suggested by JP
|
fa46cee | abs tol marker added
|
2b0fb6d | Merge branch 'u/moritz/16045' of git://trac.sagemath.org/sage into 16045
|
f5d47cf | Corrected some indentations
|
b9cb458 | Merge branch 'u/jipilab/16045' of git://trac.sagemath.org/sage into volume
|
166f0f7 | catch volume for non-compact polyhedra
|
comment:10 Changed 5 years ago by
- Status changed from needs_info to needs_review
comment:11 Changed 5 years ago by
What about:
sage: P = Polyhedron(ieqs = [[1,1,1],[-1,-1,-1],[3,1,0]]); P A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray sage: P.volume(measure='induced_rational') Traceback (most recent call last): ... RuntimeError: LattE integrale program failed (exit code -6): This is LattE integrale 1.7.3 Available from http://www.math.ucdavis.edu/~latte/ Invocation: integrate --valuation=volume --triangulate --redundancy-check=none --cdd /dev/stdin Warning: Not performing check for empty polytope, because it is unimplemented for the CDD-style input format. size = 2 x 3 Number Type = rational Ax <= b, given as (b|-A): ========================= [3 1 0] Ax = b, given as (b|-A): ======================== [1 1 1] Computing hermitean normal form. sol: [1 0] Particular solution: Basis: New inequalities: [2 -1 0] Time for reading and preprocessing: 0 sec (First dualizing back... Dualizing all cones...All cones are now dualized. Time for dualizing general cones: 0 sec done!) Triangulating cone... done. determinant: nonsquare matrix
Sage should return directly +Infinity
in this case as well.
comment:12 Changed 5 years ago by
- Status changed from needs_review to needs_work
Further, in the docstring, I would change:
* ``induced_rational``: Scaling of the Lebesgue measure for lattice polytopes
for
* ``induced_rational``: Scaling of the Lebesgue measure for rational polytopes
comment:13 Changed 5 years ago by
- Commit changed from 166f0f779d2827e3d64f82f5d9a467d51f52fab7 to b9ddbdcae276281a0119fb5849fe4b3a25208097
Branch pushed to git repo; I updated commit sha1. New commits:
b9ddbdc | catch non-compact also for 'induced_rational'
|
comment:14 Changed 5 years ago by
- Status changed from needs_work to needs_review
I did as you suggested, JP!
comment:15 Changed 5 years ago by
There is a line in a doctest that is not needed; please delete:
+ sage: v = Dexact.faces(2)[0].as_polyhedron().volume(measure='induced', engine='internal')
Otherwise, this looks good to me!
comment:16 Changed 5 years ago by
- Branch changed from u/moritz/22558 to u/saliola/22558
comment:17 Changed 5 years ago by
- Cc jipilab added
- Commit changed from b9ddbdcae276281a0119fb5849fe4b3a25208097 to 3e0ada5cae3ce4e136783784ecd6eb0cc574b9cf
- Reviewers set to Jean-Philippe Labbé, Franco Saliola
- Work issues set to run optional doctests
I made the change myself and pushed it.
JP says that the last thing to do is the run the optional tests.
New commits:
3e0ada5 | trac 22558: delete unneeded line in doctest
|
comment:18 Changed 5 years ago by
- Status changed from needs_review to positive_review
- Work issues run optional doctests deleted
Ok!
jplab$ sage -t base.py --optional=4ti2,bliss,latte_int,lidia,lrslib,mpir,normaliz,openssl,pynormaliz,python2,sage,polymake Git branch: 22558 Using --optional=4ti2,bliss,latte_int,lidia,lrslib,mpir,normaliz,openssl,polymake,pynormaliz,python2,sage Doctesting 1 file. sage -t base.py [999 tests, 157.35 s] ---------------------------------------------------------------------- All tests passed! ----------------------------------------------------------------------
Looks good to go! The bot seems to get unrelated errors. The one done at 2017-08-27 22:33:58 seems to be fine.
I set this as positive review.
comment:19 Changed 5 years ago by
- Branch changed from u/saliola/22558 to 3e0ada5cae3ce4e136783784ecd6eb0cc574b9cf
- Resolution set to fixed
- Status changed from positive_review to closed
Or zero depending on whether it is full-dimensional or not?