Polytope volume function engines produce different results

[sagetrac-wishcow]

The volume currently does not distinguish between ambient and induced volume. This should be changed.

Different engine yield very different results, and example:
The lrs engine for polytope volume calculates volume respective to the dimension of the polytope,
while the auto engine calculates volume respective to the dimension of the ambient space.

Example:

m3 = matrix(ZZ, [[0,0,0],[0,0,1]])
p = Polyhedron(m3)
p.volume(engine="lrs")
p.volume()

1.0
0

(Note: The lrs allows calculation of volumes of facets without reducing the dimension of the ambient space, but it uses non-isometrical projections!)

The suggested resolution adds a parameter measure that essentially behaves as follows:

sage: P = Polyhedron([[0, 0], [1, 1]])
sage: P.volume()
0
sage: P.volume(measure='induced')                                                                                                                                   
sqrt(2)
sage: P.volume(measure='induced_rational') # optional -- latte_int
1

Depends on #20887
Depends on #22804

CC: @sagetrac-jakobkroeker @mkoeppe @videlec @jplab @mforets @mo271 @seblabbe

Component: geometry

Keywords: polytope, volume, lrs_volume, days88

Stopgaps: wrongAnswerMarker

Author: Moritz Firsching

Branch/Commit: f5d47cf

Reviewer: Jean-Philippe Labbé

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

[sagetrac-jakobkroeker]

Stopgaps: wrongAnswerMarker

[sagetrac-jakobkroeker]

comment:1

what is a rational polytope? defined over rationals?

At least I could not get from documentation that using engine="lrs"
implies calculates volume respective to the dimension of the polytope
and using 'auto' implies calculating volume respective to the dimension of the ambient space,
so for me it is a wrong answer issue.

[jplab]

comment:2

This is actually very useful to have this. (I was actually looking for such a function just now).

It should perhaps be better documented with an optional parameter to switch this on and off and let lrs compute the volume of faces.

[mkoeppe]

comment:3

I agree, a keyword parameter that controls the measure used for lower-dim faces would be useful.
There are currently 3 options:

• 0
• answer according to standard lower-dim measure
• LattE always returns a rational answer, by normalizing with respect to the intersection lattice.

[mo271]

comment:4

A few questions:

• What should be the name for the parameter (which is essentially boolean) that controls what measure to be used?
  I can think of inherent, induced, relative, ambient... (I think instrinsic would not be a good idea.)

• Should the default for the parameter (if none is given) depend on the engine chosen?

• What should happen if the engine is not able to compute the inherent volume?

[videlec]

comment:6

Replying to @mo271:

A few questions:

• What should be the name for the parameter (which is essentially boolean) that controls what measure to be used? I can think of inherent, induced, relative, ambient... (I think instrinsic would not be a good idea.)

It is a troolean (at least for rational polytopes) as mentioned in comment:3 of Marcelo.

• Should the default for the parameter (if none is given) depend on the engine chosen?

No.

• What should happen if the engine is not able to compute the inherent volume?

A ValueError or a RuntimeError.

[mo271]

comment:8

So how about the following solve the problem:

We introduce a parameter "measure" with the following options:

• "ambient" (the default?!)
• "induced"
• "latte_renormalized" (or something that Matthias likes)

I suppose it would be wisest to catch measure="ambient" if the polytope is not full-dimensional and return "0" for all the engines (Even if the engines only can compute the induced volume of the polytope)

Should it could work like:

sage: m3 = matrix(ZZ, [[0,0,0],[0,0,1]])
sage: p = Polyhedron(m3)
sage: p.volume()
0
sage: p.volume(engine="lrs", measure="induced")
1.0
sage: p.volume(engine="lrs", measure="ambient")
0
sage: p.volume(measure="induced")
ValueError or a RuntimeError: "Please choose a different engine."

Maybe it would be ok to choose a differnt engine for the last command automatically.

What do you think?

[videlec]

comment:9

Replying to @mo271:

So how about the following solve the problem:

We introduce a parameter "measure" with the following options:

• "ambient" (the default?!)
• "induced"
• "latte_renormalized" (or something that Matthias likes)

Note that "latte_renormalized" only make sense for polyhedron defined over Q. I guess it would be better "induced_rational" rather than any reference to latte. This renormalization is very natural.

I suppose it would be wisest to catch measure="ambient" if the polytope is not full-dimensional and return "0" for all the engines (Even if the engines only can compute the induced volume of the polytope)

Should it could work like:

sage: m3 = matrix(ZZ, [[0,0,0],[0,0,1]])
sage: p = Polyhedron(m3)
sage: p.volume()
0
sage: p.volume(engine="lrs", measure="induced")
1.0
sage: p.volume(engine="lrs", measure="ambient")
0
sage: p.volume(measure="induced")
ValueError or a RuntimeError: "Please choose a different engine."

Maybe it would be ok to choose a differnt engine for the last command automatically.

+1. I also do not like the behavior of the last command. The default choice of the engine should take into account the measure argument (which should be firt BTW).

def volume(measure="ambient", engine=None):
    r"""
    Return the volume (or relative volume) of the polytope
    """

[mforets]

comment:10

minor remark: ticket #20887 also touches the polyhedron volume function

[mkoeppe]

comment:11

+1 on "induced_rational"

[mo271]

Branch: u/moritz/16045

[mo271]

Author: Moritz Firsching