Opened 4 years ago

Closed 4 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:

Status badges

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: Changed 4 years ago by novoselt

Or zero depending on whether it is full-dimensional or not?

comment:2 in reply to: ↑ 1 Changed 4 years ago by jipilab

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 4 years ago by jipilab

  • Branch set to u/jipilab/22558

comment:4 Changed 4 years ago by jipilab

  • Authors set to Jean-Philippe Labbé
  • Commit set to 0429a92cb38cc1a5aedf76eac58fba6d04f959e2
  • Status changed from new to needs_review

New commits:

0429a92Added infinite volume

comment:5 Changed 4 years ago by moritz

  • 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 4 years ago by moritz

  • Branch changed from u/jipilab/22558 to u/moritz/22558

comment:7 Changed 4 years ago by jipilab

  • Commit changed from 0429a92cb38cc1a5aedf76eac58fba6d04f959e2 to 3269ed27a9e46658dcd572f23e6e46a1703323eb
  • Dependencies set to #16045

Yes, I agree to your changes. Looks good to me.

Yes, one should first agree on #16045 and set this properly here afterwards. I put it as a dependency.


New commits:

3269ed2handle the case of non-full-dimensional polyhedra

comment:8 Changed 4 years ago by jipilab

  • Keywords days88 added

comment:9 Changed 4 years ago by git

  • Commit changed from 3269ed27a9e46658dcd572f23e6e46a1703323eb to 166f0f779d2827e3d64f82f5d9a467d51f52fab7

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

b602072add measure option
09fb035using new affine_hull function to provide induced measure
5b68b13added one forgotten line in a doctest
5f452f5doctest for 'induced_rational'
b7b10dasmall improvements suggested by JP
fa46ceeabs tol marker added
2b0fb6dMerge branch 'u/moritz/16045' of git://trac.sagemath.org/sage into 16045
f5d47cfCorrected some indentations
b9cb458Merge branch 'u/jipilab/16045' of git://trac.sagemath.org/sage into volume
166f0f7catch volume for non-compact polyhedra

comment:10 Changed 4 years ago by moritz

  • Authors changed from Jean-Philippe Labbé to Moritz Firsching
  • Status changed from needs_info to needs_review

comment:11 Changed 4 years ago by jipilab

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.

Last edited 4 years ago by jipilab (previous) (diff)

comment:12 Changed 4 years ago by jipilab

  • 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 4 years ago by git

  • Commit changed from 166f0f779d2827e3d64f82f5d9a467d51f52fab7 to b9ddbdcae276281a0119fb5849fe4b3a25208097

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

b9ddbdccatch non-compact also for 'induced_rational'

comment:14 Changed 4 years ago by moritz

  • Status changed from needs_work to needs_review

I did as you suggested, JP!

comment:15 Changed 4 years ago by saliola

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 4 years ago by saliola

  • Branch changed from u/moritz/22558 to u/saliola/22558

comment:17 Changed 4 years ago by saliola

  • 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:

3e0ada5trac 22558: delete unneeded line in doctest

comment:18 Changed 4 years ago by jipilab

  • 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 4 years ago by vbraun

  • Branch changed from u/saliola/22558 to 3e0ada5cae3ce4e136783784ecd6eb0cc574b9cf
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.