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

[jipilab]

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.

[novoselt]

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

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

[jipilab]

New commits:

​0429a92

Added infinite volume

[moritz]

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.

[jipilab]

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

[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

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

[jipilab]

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

[git]

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

​b9ddbdc

catch non-compact also for 'induced_rational'

[moritz]

I did as you suggested, JP!

[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!

[saliola]

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

[jipilab]

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.