.volume() of polyhedron does not handle unbounded polyhedron properly

[jplab]

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.

Depends on #16045

CC: @fchapoton @videlec @mkoeppe @mo271 @jplab

Component: geometry

Keywords: days84, volume, days88

Author: Moritz Firsching

Branch/Commit: 3e0ada5

Reviewer: Jean-Philippe Labbé, Franco Saliola

Issue created by migration from https://trac.sagemath.org/ticket/22558

[novoselt]

comment:1

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

[jplab]

comment:2

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...

[jplab]

Branch: u/jipilab/22558

[jplab]

New commits:

0429a92

Added infinite volume

[jplab]

Commit: 0429a92

[jplab]

Author: Jean-Philippe Labbé

[mo271]

comment:5

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.

[mo271]

Changed branch from u/jipilab/22558 to u/moritz/22558

[jplab]

comment:7

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:

3269ed2

handle the case of non-full-dimensional polyhedra

[jplab]

Dependencies: #16045

[jplab]

Changed commit from 0429a92 to 3269ed2

[jplab]

Changed keywords from days84, volume to days84, volume, days88

[sagetrac-git]

Changed commit from 3269ed2 to 166f0f7

[sagetrac-git]

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

[mo271]

Changed author from Jean-Philippe Labbé to Moritz Firsching

[jplab]

comment:11

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.

[jplab]

comment:12

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

[sagetrac-git]

Changed commit from 166f0f7 to b9ddbdc

[sagetrac-git]

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

b9ddbdc

catch non-compact also for 'induced_rational'

[mo271]

comment:14

I did as you suggested, JP!

[saliola]

comment:15

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!

[saliola]

Changed branch from u/moritz/22558 to u/saliola/22558

[saliola]

comment:17

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

[saliola]

Work Issues: run optional doctests

[saliola]

Changed commit from b9ddbdc to 3e0ada5

[saliola]

Reviewer: Jean-Philippe Labbé, Franco Saliola

[jplab]

Changed work issues from run optional doctests to none

[jplab]

comment:18

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.

[vbraun]

Changed branch from u/saliola/22558 to 3e0ada5