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:  sage7.6 
Component:  geometry  Keywords:  days84, geometry, volume, days88 
Cc:  chapoton, vdelecroix, mkoeppe, moritz, jipilab  Merged in:  
Authors:  Moritz Firsching  Reviewers:  JeanPhilippe 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 followup: ↓ 2 Changed 5 years ago by
comment:2 in reply to: ↑ 1 Changed 5 years ago by
Or zero depending on whether it is fulldimensional 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 noncompact nonfulldimensional 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 1dimensional 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 noncompact 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 1dimensional 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 redundancycheck=none cdd /dev/stdin Warning: Not performing check for empty polytope, because it is unimplemented for the CDDstyle input format. size = 2 x 3 Number Type = rational Ax <= b, given as (bA): ========================= [3 1 0] Ax = b, given as (bA): ======================== [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 noncompact 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 JeanPhilippe 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 20170827 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 fulldimensional or not?