Sage: Ticket #16045: Polytope volume function engines produce different results
https://trac.sagemath.org/ticket/16045
<p>
The volume currently does not distinguish between ambient and induced volume. This should be changed.
</p>
<p>
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.
</p>
<p>
Example:
</p>
<pre class="wiki">m3 = matrix(ZZ, [[0,0,0],[0,0,1]])
p = Polyhedron(m3)
p.volume(engine="lrs")
p.volume()
1.0
0
</pre><p>
(Note: The lrs allows calculation of volumes of facets without reducing the dimension of the ambient space, but it uses non-isometrical projections!)
</p>
<p>
The suggested resolution adds a parameter <code>measure</code> that essentially behaves as follows:
</p>
<pre class="wiki">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
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/16045
Trac 1.1.6jakobkroekerSat, 04 Mar 2017 00:22:56 GMTcc, stopgaps set
https://trac.sagemath.org/ticket/16045#comment:1
https://trac.sagemath.org/ticket/16045#comment:1
<ul>
<li><strong>cc</strong>
<em>jakobkroeker</em> added
</li>
<li><strong>stopgaps</strong>
set to <em>wrongAnswerMarker</em>
</li>
</ul>
<p>
what is a rational polytope? defined over rationals?
</p>
<p>
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.
</p>
TicketjipilabThu, 09 Mar 2017 18:30:58 GMTcc changed
https://trac.sagemath.org/ticket/16045#comment:2
https://trac.sagemath.org/ticket/16045#comment:2
<ul>
<li><strong>cc</strong>
<em>mkoeppe</em> <em>vdelecroix</em> <em>jipilab</em> added
</li>
</ul>
<p>
This is actually very useful to have this. (I was actually looking for such a function just now).
</p>
<p>
It should perhaps be better documented with an optional parameter to switch this on and off and let <code>lrs</code> compute the volume of faces.
</p>
TicketmkoeppeThu, 09 Mar 2017 18:35:51 GMTcc changed
https://trac.sagemath.org/ticket/16045#comment:3
https://trac.sagemath.org/ticket/16045#comment:3
<ul>
<li><strong>cc</strong>
<em>mforets</em> added
</li>
</ul>
<p>
I agree, a keyword parameter that controls the measure used for lower-dim faces would be useful.
There are currently 3 options:
</p>
<ul><li>0
</li><li>answer according to standard lower-dim measure
</li><li>LattE always returns a rational answer, by normalizing with respect to the intersection lattice.
</li></ul>
TicketmoritzSun, 12 Mar 2017 23:04:04 GMT
https://trac.sagemath.org/ticket/16045#comment:4
https://trac.sagemath.org/ticket/16045#comment:4
<p>
A few questions:
</p>
<ul><li>What should be the name for the parameter (which is essentially boolean) that controls what measure to be used?
</li></ul><p>
I can think of <code>inherent</code>, <code>induced</code>, <code>relative</code>, <code>ambient</code>... (I think <code>instrinsic</code> would not be a good idea.)
</p>
<ul><li>Should the default for the parameter (if none is given) depend on the <code>engine</code> chosen?
</li><li>What should happen if the <code>engine</code> is not able to compute the inherent volume?
</li></ul>
TicketmoritzSun, 12 Mar 2017 23:06:21 GMTcc changed
https://trac.sagemath.org/ticket/16045#comment:5
https://trac.sagemath.org/ticket/16045#comment:5
<ul>
<li><strong>cc</strong>
<em>moritz</em> added
</li>
</ul>
TicketvdelecroixTue, 14 Mar 2017 12:23:24 GMT
https://trac.sagemath.org/ticket/16045#comment:6
https://trac.sagemath.org/ticket/16045#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16045#comment:4" title="Comment 4">moritz</a>:
</p>
<blockquote class="citation">
<p>
A few questions:
</p>
<ul><li>What should be the name for the parameter (which is essentially boolean) that controls what measure to be used? I can think of <code>inherent</code>, <code>induced</code>, <code>relative</code>, <code>ambient</code>... (I think <code>instrinsic</code> would not be a good idea.)
</li></ul></blockquote>
<p>
It is a troolean (at least for rational polytopes) as mentioned in <a class="ticket" href="https://trac.sagemath.org/ticket/16045#comment:3" title="Comment 3">comment:3</a> of Marcelo.
</p>
<blockquote class="citation">
<ul><li>Should the default for the parameter (if none is given) depend on the <code>engine</code> chosen?
</li></ul></blockquote>
<p>
No.
</p>
<blockquote class="citation">
<ul><li>What should happen if the <code>engine</code> is not able to compute the inherent volume?
</li></ul></blockquote>
<p>
A <code>ValueError</code> or a <code>RuntimeError</code>.
</p>
TicketslabbeWed, 15 Mar 2017 13:41:08 GMTcc changed
https://trac.sagemath.org/ticket/16045#comment:7
https://trac.sagemath.org/ticket/16045#comment:7
<ul>
<li><strong>cc</strong>
<em>slabbe</em> added
</li>
</ul>
TicketmoritzThu, 16 Mar 2017 17:41:21 GMT
https://trac.sagemath.org/ticket/16045#comment:8
https://trac.sagemath.org/ticket/16045#comment:8
<p>
So how about the following solve the problem:
</p>
<p>
We introduce a parameter "measure" with the following options:
</p>
<ul><li>"ambient" (the default?!)
</li><li>"induced"
</li><li>"latte_renormalized" (or something that Matthias likes)
</li></ul><p>
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)
</p>
<p>
Should it could work like:
</p>
<pre class="wiki">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."
</pre><p>
Maybe it would be ok to choose a differnt engine for the last command automatically.
</p>
<p>
What do you think?
</p>
TicketvdelecroixThu, 16 Mar 2017 17:58:20 GMT
https://trac.sagemath.org/ticket/16045#comment:9
https://trac.sagemath.org/ticket/16045#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16045#comment:8" title="Comment 8">moritz</a>:
</p>
<blockquote class="citation">
<p>
So how about the following solve the problem:
</p>
<p>
We introduce a parameter "measure" with the following options:
</p>
<ul><li>"ambient" (the default?!)
</li><li>"induced"
</li><li>"latte_renormalized" (or something that Matthias likes)
</li></ul></blockquote>
<p>
Note that "latte_renormalized" only make sense for polyhedron defined over Q. I guess it would be better <code>"induced_rational"</code> rather than any reference to latte. This renormalization is very natural.
</p>
<blockquote class="citation">
<p>
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)
</p>
<p>
Should it could work like:
</p>
<pre class="wiki">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."
</pre><p>
Maybe it would be ok to choose a differnt engine for the last command automatically.
</p>
</blockquote>
<p>
+1. I also do not like the behavior of the last command. The default choice of the engine should take into account the <code>measure</code> argument (which should be firt BTW).
</p>
<pre class="wiki">def volume(measure="ambient", engine=None):
r"""
Return the volume (or relative volume) of the polytope
"""
</pre>
TicketmforetsThu, 16 Mar 2017 18:19:42 GMT
https://trac.sagemath.org/ticket/16045#comment:10
https://trac.sagemath.org/ticket/16045#comment:10
<p>
minor remark: ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/20887" title="enhancement: Integration of polynomials over polytopes with LattE (closed: fixed)">#20887</a> also touches the polyhedron volume function
</p>
TicketmkoeppeThu, 16 Mar 2017 18:36:09 GMT
https://trac.sagemath.org/ticket/16045#comment:11
https://trac.sagemath.org/ticket/16045#comment:11
<p>
+1 on <code>"induced_rational"</code>
</p>
TicketmoritzFri, 31 Mar 2017 15:59:37 GMTbranch set
https://trac.sagemath.org/ticket/16045#comment:12
https://trac.sagemath.org/ticket/16045#comment:12
<ul>
<li><strong>branch</strong>
set to <em>u/moritz/16045</em>
</li>
</ul>
TicketmoritzFri, 31 Mar 2017 16:03:01 GMTstatus changed; commit, author set
https://trac.sagemath.org/ticket/16045#comment:13
https://trac.sagemath.org/ticket/16045#comment:13
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_info</em>
</li>
<li><strong>commit</strong>
set to <em>2e2764eed2b78dde93138f613ca98712ecc9d3e4</em>
</li>
<li><strong>author</strong>
set to <em>Moritz Firsching</em>
</li>
</ul>
<p>
I am building on <a class="closed ticket" href="https://trac.sagemath.org/ticket/20887" title="enhancement: Integration of polynomials over polytopes with LattE (closed: fixed)">#20887</a> and introduced a <code>measure</code> option.
</p>
<p>
Here is a test (make sure ou have latte_int, topcom and lrs installed)
</p>
<pre class="wiki">sage: C = polytopes.cube()
sage: P = polytopes.permutahedron(4)
sage: P
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 24 vertices
sage: measures = ["ambient", "induced", "induced_rational"]
sage: engines = ["auto", "internal", "TOPCOM", "lrs", "latte"]
sage: for m in measures:
....: for e in engines:
....: try:
....: pvol = P.volume(measure=m, engine=e)
....: except TypeError as err:
....: pvol = err
....: try:
....: cvol = C.volume(measure=m, engine=e)
....: except Exception as err:
....: cvol = err
....: print 'measure =',m, 'engine =',e
....: print 'not-fulldimensional example: ', pvol
....: print 'full-dimensional example: ', cvol
....: print '--------------'
....:
measure = ambient engine = auto
not-fulldimensional example: 0
full-dimensional example: 8
--------------
measure = ambient engine = internal
not-fulldimensional example: 0
full-dimensional example: 8
--------------
measure = ambient engine = TOPCOM
not-fulldimensional example: 0
full-dimensional example: 8
--------------
measure = ambient engine = lrs
not-fulldimensional example: 0
full-dimensional example: 8.0
--------------
measure = ambient engine = latte
not-fulldimensional example: 0
full-dimensional example: 8
--------------
measure = induced engine = auto
not-fulldimensional example: 16.0
full-dimensional example: 8.0
--------------
measure = induced engine = internal
not-fulldimensional example: The induced measure can only be computed with the engine set to `auto` or `lrs`
full-dimensional example: 8.0
--------------
measure = induced engine = TOPCOM
not-fulldimensional example: The induced measure can only be computed with the engine set to `auto` or `lrs`
full-dimensional example: 8.0
--------------
measure = induced engine = lrs
not-fulldimensional example: 16.0
full-dimensional example: 8.0
--------------
measure = induced engine = latte
not-fulldimensional example: The induced measure can only be computed with the engine set to `auto` or `lrs`
full-dimensional example: 8.0
--------------
measure = induced_rational engine = auto
not-fulldimensional example: 16
full-dimensional example: 8
--------------
measure = induced_rational engine = internal
not-fulldimensional example: The induced rational measure can only be computed with the engine set to `auto` or `latte`
full-dimensional example: 8
--------------
measure = induced_rational engine = TOPCOM
not-fulldimensional example: The induced rational measure can only be computed with the engine set to `auto` or `latte`
full-dimensional example: 8
--------------
measure = induced_rational engine = lrs
not-fulldimensional example: The induced rational measure can only be computed with the engine set to `auto` or `latte`
full-dimensional example: 8
--------------
measure = induced_rational engine = latte
not-fulldimensional example: 16
full-dimensional example: 8
--------------
</pre><p>
The options are explained as
</p>
<pre class="wiki"> - ``measure`` -- string. The measure to use. Allowed values are:
* ``ambient``: Lebesgue measure of ambient space (volume)
* ``induced``: Lebesgue measure of affine hull (relative volume)
* ``induced_rational``: TODO: explanation (only makes sense for integer polytopes?!)
- ``engine`` -- string. The backend to use. Allowed values are:
* ``'auto'`` (default): choose engine according to measure
* ``'internal'``: see :meth:`triangulate`.
* ``'TOPCOM'``: see :meth:`triangulate`.
* ``'lrs'``: use David Avis's lrs program (optional).
* ``'latte'``: use LattE integrale program (optional).
</pre><p>
What could I write for <code>induced_rational</code>?
</p>
<p>
I have not yet added doctests.
</p>
<p>
Comments welcome!
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=17911f7051d618046f8ed37681b6f4516ec751b3"><span class="icon"></span>17911f7</a></td><td><code>Added integrate method to Polyhedron base.py</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=91d885edbccb92d581781c72f3c5eeb94417d0b8"><span class="icon"></span>91d885e</a></td><td><code>Fix the docstrings, and enhance integrate method.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=507aea5adb6f05ddc95cfef7cd79d24d3041de10"><span class="icon"></span>507aea5</a></td><td><code>Add the new volume engine Polyhedron.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=a563192b0dcbce9ab4e1387a1f3435e5d179cbc9"><span class="icon"></span>a563192</a></td><td><code>fix a bug in _volume_latte</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=9ac82796710a0dfd1b99d95addf78cdfc1b37652"><span class="icon"></span>9ac8279</a></td><td><code>reject RDF, but add an example</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=ec1589760e046f6cd18ead736b36338a18b84d74"><span class="icon"></span>ec15897</a></td><td><code>add test for low-dim polytope and fix docstring typo</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=1cf59f415161bb1901c0a1894fc9166dd0d90153"><span class="icon"></span>1cf59f4</a></td><td><code>fix last doctest in integrate (exception mismatch)</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=dc544fac24882973b51a5e6c8c645ace92da1dd0"><span class="icon"></span>dc544fa</a></td><td><code>fix optional tag in integrate test</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=31ea1481446d570919f13cc08efdf34e8570df98"><span class="icon"></span>31ea148</a></td><td><code>Merge branch 'u/mforets/20887' of git://trac.sagemath.org/sage into 16045</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=2e2764eed2b78dde93138f613ca98712ecc9d3e4"><span class="icon"></span>2e2764e</a></td><td><code>add measure option</code>
</td></tr></table>
TicketvdelecroixFri, 31 Mar 2017 16:07:25 GMT
https://trac.sagemath.org/ticket/16045#comment:14
https://trac.sagemath.org/ticket/16045#comment:14
<blockquote class="citation">
<p>
What could I write for induced_rational?
</p>
</blockquote>
<p>
(I think this is describe in the latte manual) Given the polytope P in Z<sup>d</sup> it spans an affine space E. The ambient measure is the only scaling of the Lebesgue measure so that the lattice <code>E \cap Z^d</code> has covolume 1 in E.
</p>
TicketvdelecroixFri, 31 Mar 2017 16:11:38 GMT
https://trac.sagemath.org/ticket/16045#comment:15
https://trac.sagemath.org/ticket/16045#comment:15
<p>
If you merge commits from <a class="closed ticket" href="https://trac.sagemath.org/ticket/20887" title="enhancement: Integration of polynomials over polytopes with LattE (closed: fixed)">#20887</a> here you should set it as a dependency.
</p>
TicketmkoeppeFri, 31 Mar 2017 16:14:09 GMT
https://trac.sagemath.org/ticket/16045#comment:16
https://trac.sagemath.org/ticket/16045#comment:16
<p>
Note that it's also defined for rational polytopes; and more generally for any (possibly irrational) translation of those.
</p>
TicketmoritzFri, 31 Mar 2017 17:59:24 GMTdependencies set
https://trac.sagemath.org/ticket/16045#comment:17
https://trac.sagemath.org/ticket/16045#comment:17
<ul>
<li><strong>dependencies</strong>
set to <em>#20887</em>
</li>
</ul>
TicketmkoeppeSun, 02 Apr 2017 18:15:58 GMTstatus changed
https://trac.sagemath.org/ticket/16045#comment:18
https://trac.sagemath.org/ticket/16045#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_work</em>
</li>
</ul>
TicketmoritzMon, 03 Apr 2017 09:01:53 GMT
https://trac.sagemath.org/ticket/16045#comment:19
https://trac.sagemath.org/ticket/16045#comment:19
<p>
I noticed that "lrs" is in fact <strong>not</strong> computing the Lebesgue measure of the affine hull. Form the lrs web-page:
</p>
<blockquote>
<p>
If the option is applied to a V-representation of a polytope that is not full dimensional, the volume of a projected polytope is computed. The projection used is to the lexicographically smallest coordinate subspace, see Avis, Fukuda, Picozzi (2002).
</p>
</blockquote>
<p>
In fact, this shows already in one of the old doctests:
</p>
<pre class="wiki">sage: I = Polyhedron([(0,0), (1,1)])
sage: I.volume(engine='lrs') #optional - lrslib
1.0
</pre><p>
The result with the induced measure should be <code>sqrt(2)</code> (or <code>1.414213562373095</code> I guess)
</p>
<p>
So this should not be used to compute the volume of facets, as mentioned in <a class="ticket" href="https://trac.sagemath.org/ticket/16045#comment:2" title="Comment 2">comment:2</a> !
</p>
<p>
In any case I still think it would be useful to have the option for this measure, except that at the moment, none of the engines is able to actually compute appropriate induced volumes.
</p>
<p>
Perhaps it would be useful to open a ticket to ask for a function, that does compute the induced measure?! A naive implementation could choose an affine basis of vertices and then some isometry.
</p>
TicketjipilabTue, 04 Apr 2017 07:41:45 GMT
https://trac.sagemath.org/ticket/16045#comment:20
https://trac.sagemath.org/ticket/16045#comment:20
<p>
It would be nice to have an explanation of these subtleties in the doc of the function (as shown by Moritz). Consequently, the issue described in the ticket would be resolved so as to address the reason why it returns different results.
</p>
<p>
IMHO, I guess it is okay to have one method returning different results depending on the value of the parameters. So +1 to have an optional parameter which specifies the measure (and hence the engine in some cases) as Vincent mentionned.
</p>
<p>
Finally, add a TODO that would ask for the lebesgue measure which would be addressed in a separate ticket and explain what <code>lrs</code> is doing with a possible link to the webpage.
</p>
<p>
What do you think?
</p>
TicketmoritzWed, 12 Apr 2017 09:12:42 GMT
https://trac.sagemath.org/ticket/16045#comment:21
https://trac.sagemath.org/ticket/16045#comment:21
<p>
One thing that would be useful to have, would be a function, that takes a non full-dimensional poytope and returns a full-dimensional one that is affinely equivalent to the original one. Note that the usual <code>.affine_hull</code> method does not achive that goal:
</p>
<pre class="wiki">sage: p = Polyhedron([[0,0],[1,1]])
sage: p.affine_hull()
A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices
sage: p.affine_hull().vertices()
(A vertex at (0), A vertex at (1))
</pre><p>
The length of the affine hull is not <code>sqrt(2)</code> as one might expect. Another example would be
</p>
<pre class="wiki">sage: s = polytopes.simplex()
sage: s
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices
sage: s.affine_hull()
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: _.show()
Launched jmol viewer for Graphics3d Object
</pre><p>
Here the simplex is not regular after using <code>.affine_hull</code>.
</p>
<p>
Consider this new <code>affine_hull</code> function:
</p>
<pre class="wiki">def affine_hull(P, preserve_volume=True):
if P.ambient_dim() == P.dim():
return P
Q = P.translation(-vector(P.vertices()[0]))
v = Q.vertices()[0]
assert list(v) == P.ambient_dim()*[0]
import itertools
M = Matrix([list(w) for w in itertools.islice(v.neighbors(), P.dim())])
if P.base_ring() in [ZZ,QQ]:
M = Matrix(AA,M)
A = M.gram_schmidt(orthonormal = True)[0]
return Polyhedron([A*vector(v) for v in Q.vertices()])
</pre><p>
Using this gets the desired results:
</p>
<pre class="wiki">sage: p = Polyhedron([[0,0],[1,1]])
sage: affine_hull(p)
A 1-dimensional polyhedron in AA^1 defined as the convex hull of 2 vertices
sage: affine_hull(p).vertices()
(A vertex at (0), A vertex at (1.414213562373095?))
</pre><p>
It is actually useful to plot the permutahedron nicely:
</p>
<pre class="wiki">sage: P = polytopes.permutahedron(4)
sage: P
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 24 vertices
sage: affine_hull(P)
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
sage: _.plot()
Launched jmol viewer for Graphics3d Object
</pre><blockquote>
<p>
(There is an inherent problem, that considering a rational polytope as full-dimensional polytope in its affine hull might lead to non-rational polyopes: basically you want to work in a field with square roots.)
</p>
</blockquote>
<p>
In any case I propose to introduce an improved version of the <code>.affine_hull</code> method, perhaps with an parameter <code>preserve_volume=True</code> (or <code>isometry=True</code>) an then use this method to handle the cases of the volume of non full-dimenional polytopes here.
</p>
<p>
What do you think?
</p>
TicketvdelecroixWed, 12 Apr 2017 09:36:27 GMT
https://trac.sagemath.org/ticket/16045#comment:22
https://trac.sagemath.org/ticket/16045#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16045#comment:21" title="Comment 21">moritz</a>:
</p>
<blockquote class="citation">
<p>
One thing that would be useful to have, would be a function, that takes a non full-dimensional poytope and returns a full-dimensional one that is affinely equivalent to the original one.
</p>
<p>
[...]
</p>
<p>
What do you think?
</p>
</blockquote>
<p>
I agree that it would be useful and essentially straightforward (ignoring details about base ring). You can open a <strong>new</strong> ticket and move the discussion there.
</p>
TicketmoritzThu, 13 Apr 2017 11:58:35 GMT
https://trac.sagemath.org/ticket/16045#comment:23
https://trac.sagemath.org/ticket/16045#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16045#comment:22" title="Comment 22">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
I agree that it would be useful and essentially straightforward (ignoring details about base ring). You can open a <strong>new</strong> ticket and move the discussion there.
</p>
</blockquote>
<p>
I opened <a class="closed ticket" href="https://trac.sagemath.org/ticket/22804" title="enhancement: add orthogonal/orthonormal feature to affine_hull of polyhedra (closed: fixed)">#22804</a> and already added some code. This could eventually become a depency here (<a class="closed ticket" href="https://trac.sagemath.org/ticket/16045" title="defect: Polytope volume function engines produce different results (closed: fixed)">#16045</a>) and we can end up with a '.volume' method that is more useful...
</p>
TicketmoritzMon, 26 Jun 2017 19:57:52 GMTdependencies changed
https://trac.sagemath.org/ticket/16045#comment:24
https://trac.sagemath.org/ticket/16045#comment:24
<ul>
<li><strong>dependencies</strong>
changed from <em>#20887</em> to <em>#20887 #22804</em>
</li>
</ul>
TicketgitThu, 29 Jun 2017 18:59:23 GMTcommit changed
https://trac.sagemath.org/ticket/16045#comment:25
https://trac.sagemath.org/ticket/16045#comment:25
<ul>
<li><strong>commit</strong>
changed from <em>2e2764eed2b78dde93138f613ca98712ecc9d3e4</em> to <em>7a728f10bf75e2e1233a2901e6b831336b5f38f2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=f14a9e83227a504b051af98f4d2c381961512545"><span class="icon"></span>f14a9e8</a></td><td><code>add measure option</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=7a728f10bf75e2e1233a2901e6b831336b5f38f2"><span class="icon"></span>7a728f1</a></td><td><code>using new affine_hull function to provide induced measure</code>
</td></tr></table>
TicketgitThu, 29 Jun 2017 19:03:52 GMTcommit changed
https://trac.sagemath.org/ticket/16045#comment:26
https://trac.sagemath.org/ticket/16045#comment:26
<ul>
<li><strong>commit</strong>
changed from <em>7a728f10bf75e2e1233a2901e6b831336b5f38f2</em> to <em>1f64267248f427828b1d0225b947086b8540e619</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=1f64267248f427828b1d0225b947086b8540e619"><span class="icon"></span>1f64267</a></td><td><code>added one forgotten line in a doctest</code>
</td></tr></table>
TicketmoritzThu, 29 Jun 2017 19:13:32 GMTstatus, description changed
https://trac.sagemath.org/ticket/16045#comment:27
https://trac.sagemath.org/ticket/16045#comment:27
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_info</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/16045?action=diff&version=27">diff</a>)
</li>
</ul>
<p>
I now used the new affine hull function to provide induced volumes; comments welcome!
</p>
<p>
I would like to include a good example / doctest for the induced rational volume, any hints? (Also to improve the description ind the section "Input"?)
</p>
TicketvdelecroixThu, 29 Jun 2017 22:29:18 GMT
https://trac.sagemath.org/ticket/16045#comment:28
https://trac.sagemath.org/ticket/16045#comment:28
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16045#comment:27" title="Comment 27">moritz</a>:
</p>
<blockquote class="citation">
<p>
I now used the new affine hull function to provide induced volumes; comments welcome!
</p>
<p>
I would like to include a good example / doctest for the induced rational volume, any hints? (Also to improve the description ind the section "Input"?)
</p>
</blockquote>
<p>
Volume of the line segment between <code>(a,0)</code> and <code>(0,b)</code> are already good examples. Then you can do that for the triangle <code>(a,0,0)</code>, <code>(0,b,0)</code> and <code>(0,0,c)</code>. And you can consider polytopes obtained by permuting the entries of a vector like
</p>
<pre class="wiki">sage: Polyhedron(vertices=[(0,0,1,1),(0,1,1,0),(1,1,0,0)])
A 2-dimensional polyhedron in ZZ^4 defined as the convex hull of 3 vertices
</pre>
TicketgitFri, 30 Jun 2017 08:14:00 GMTcommit changed
https://trac.sagemath.org/ticket/16045#comment:29
https://trac.sagemath.org/ticket/16045#comment:29
<ul>
<li><strong>commit</strong>
changed from <em>1f64267248f427828b1d0225b947086b8540e619</em> to <em>545507350c90451a2532b5d082fb09ecf2f031fb</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=545507350c90451a2532b5d082fb09ecf2f031fb"><span class="icon"></span>5455073</a></td><td><code>doctest for 'induced_rational'</code>
</td></tr></table>
TicketmoritzMon, 03 Jul 2017 09:36:56 GMTstatus changed
https://trac.sagemath.org/ticket/16045#comment:30
https://trac.sagemath.org/ticket/16045#comment:30
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
TicketjipilabWed, 12 Jul 2017 09:48:28 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/16045#comment:31
https://trac.sagemath.org/ticket/16045#comment:31
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jean-Philippe Labbé</em>
</li>
</ul>
<p>
Hi Moritz,
</p>
<p>
Small comments:
</p>
<ul><li>In the doc: <code>measure.Different engines</code> (add space)
</li><li>Further, right after this sentence, could there be a short sentence, maybe as a note, to say what "for lattice polytope" means exactly?.
</li><li>For the example, <code>P = Polyhedron([[0, 0], [1, 1]])</code> I would also add the output with the parameter <code>induced_rational</code>. This will make it contrast right away, rather than waiting for polyhedron <code>I</code>. (It is minor but very instructive).
</li><li> Perhaps name the second polyhedron <code>P</code> differently.
</li><li><code>if polyhedron is actually full-dimensional, return volume with ambient measuren</code> (remove the <code>n</code> at the end).
</li></ul><p>
You have some failed tests:
</p>
<pre class="wiki"> **********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 4373, in sage.geometry.polyhedron.base.Polyhedron_base.volume
Failed example:
w = Dinexact.faces(2)[0].as_polyhedron().volume(measure='induced', engine='internal'); w
Expected:
1.534062710738235
Got:
1.5340627107382352
</pre><pre class="wiki">Failed example:
I.volume(measure='induced_rational')
Exception raised:
NotImplementedError: You must install the optional latte_int package for this function to work.
</pre><p>
(add <code># optional -- latte_int</code>)
</p>
TicketgitThu, 13 Jul 2017 19:31:35 GMTcommit changed
https://trac.sagemath.org/ticket/16045#comment:32
https://trac.sagemath.org/ticket/16045#comment:32
<ul>
<li><strong>commit</strong>
changed from <em>545507350c90451a2532b5d082fb09ecf2f031fb</em> to <em>1a8cefc5171c26c4fa27a198a48dd6a661fd59b0</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=e5a01d04f8fb4ceba17d7aece422568f74232555"><span class="icon"></span>e5a01d0</a></td><td><code>add measure option</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=9350ef29f0bff8f7a58fb26e506b420282852755"><span class="icon"></span>9350ef2</a></td><td><code>using new affine_hull function to provide induced measure</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=bddd3edf691119965d3e40a44c541a9f36457692"><span class="icon"></span>bddd3ed</a></td><td><code>added one forgotten line in a doctest</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=a4e62a9b1580d6864ba2f67725fb79c21f149c56"><span class="icon"></span>a4e62a9</a></td><td><code>doctest for 'induced_rational'</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=1a8cefc5171c26c4fa27a198a48dd6a661fd59b0"><span class="icon"></span>1a8cefc</a></td><td><code>small improvements suggested by JP</code>
</td></tr></table>
TicketmoritzThu, 13 Jul 2017 19:36:52 GMTstatus changed
https://trac.sagemath.org/ticket/16045#comment:33
https://trac.sagemath.org/ticket/16045#comment:33
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_info</em>
</li>
</ul>
<p>
Thanks for the comments, JP!
</p>
<p>
I fixed everything, except perhaps the following; where I was not quite sure what is going on. (Perhaps somehow different machines have different ideas what a real double is..)
</p>
<pre class="wiki"> w = Dinexact.faces(2)[0].as_polyhedron().volume(measure='induced', engine='internal'); w
Expected:
1.534062710738235
Got:
1.5340627107382352
</pre><p>
I hope I managed to add <code># optional -- latte_int</code> in all relevant places: I didn't test it without <code>latte_int</code> installed.
</p>
TicketslabbeMon, 17 Jul 2017 08:46:59 GMT
https://trac.sagemath.org/ticket/16045#comment:34
https://trac.sagemath.org/ticket/16045#comment:34
<p>
Use <a class="ext-link" href="https://github.com/sagemath/sage/blob/develop/src/sage/symbolic/integration/integral.py#L726"><span class="icon"></span># abs tol</a> marker in the comment. See <a class="ext-link" href="http://doc.sagemath.org/html/en/developer/coding_basics.html#special-markup-to-influence-doctests"><span class="icon"></span>Special Markup to Influence Doctests</a> in the documentation.
</p>
TicketgitMon, 17 Jul 2017 11:17:53 GMTcommit changed
https://trac.sagemath.org/ticket/16045#comment:35
https://trac.sagemath.org/ticket/16045#comment:35
<ul>
<li><strong>commit</strong>
changed from <em>1a8cefc5171c26c4fa27a198a48dd6a661fd59b0</em> to <em>fa46ceef2634458cd6dfc4146feb65f1945ea5a2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=b6020721bdab27cf505c6c2a454e864a43d84d63"><span class="icon"></span>b602072</a></td><td><code>add measure option</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=09fb0356c4987e9fcec2a19a955c9b9038f0b474"><span class="icon"></span>09fb035</a></td><td><code>using new affine_hull function to provide induced measure</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=5b68b132649156c3e64a886675d757a3326f9627"><span class="icon"></span>5b68b13</a></td><td><code>added one forgotten line in a doctest</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=5f452f555c39bd58b44adde9beaafa7070d780ff"><span class="icon"></span>5f452f5</a></td><td><code>doctest for 'induced_rational'</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=b7b10da97e58a9f8a3ce4ecad890a1ee5b56344b"><span class="icon"></span>b7b10da</a></td><td><code>small improvements suggested by JP</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=fa46ceef2634458cd6dfc4146feb65f1945ea5a2"><span class="icon"></span>fa46cee</a></td><td><code>abs tol marker added</code>
</td></tr></table>
TicketmoritzMon, 17 Jul 2017 11:24:45 GMTstatus changed
https://trac.sagemath.org/ticket/16045#comment:36
https://trac.sagemath.org/ticket/16045#comment:36
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Thanks, Sébastian!
I added the marker..
</p>
TicketjipilabMon, 21 Aug 2017 16:18:04 GMTkeywords changed
https://trac.sagemath.org/ticket/16045#comment:37
https://trac.sagemath.org/ticket/16045#comment:37
<ul>
<li><strong>keywords</strong>
<em>days88</em> added
</li>
</ul>
TicketjipilabMon, 21 Aug 2017 21:48:01 GMT
https://trac.sagemath.org/ticket/16045#comment:38
https://trac.sagemath.org/ticket/16045#comment:38
<p>
There is a hidden failed test (probably got caught by chance by the bot):
</p>
<pre class="wiki">sage -t --long src/sage/geometry/polyhedron/backend_normaliz.py
**********************************************************************
File "src/sage/geometry/polyhedron/backend_normaliz.py", line 412, in sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz.integral_hull
Failed example:
set(PI.Vrepresentation()) # optional - pynormaliz
Expected:
{A vertex at (-1, 0), A vertex at (0, 1), A ray in the direction (1, 0)}
Got:
{A ray in the direction (1, 0), A vertex at (-1, 0), A vertex at (0, 1)}
**********************************************************************
File "src/sage/geometry/polyhedron/backend_normaliz.py", line 420, in sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz.integral_hull
Failed example:
set(PI.Vrepresentation()) # optional - pynormaliz
Expected:
{A vertex at (1, 0),
A ray in the direction (1, 0),
A line in the direction (1, -1)}
Got:
{A line in the direction (1, -1),
A ray in the direction (1, 0),
A vertex at (1, 0)}
**********************************************************************
1 item had failures:
2 of 10 in sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz.integral_hull
[100 tests, 2 failures, 4.39 s]
</pre><p>
Question: I have "normaliz" in my optional installed packages but not "pynormaliz", is the above naming correct then?
</p>
<p>
I am aware that this is not the topic of this ticket but since the tests failed here, it is probably best to treat this here.
</p>
TicketjipilabMon, 21 Aug 2017 22:09:16 GMTstatus changed
https://trac.sagemath.org/ticket/16045#comment:39
https://trac.sagemath.org/ticket/16045#comment:39
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketmkoeppeTue, 22 Aug 2017 04:53:21 GMT
https://trac.sagemath.org/ticket/16045#comment:40
https://trac.sagemath.org/ticket/16045#comment:40
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16045#comment:38" title="Comment 38">jipilab</a>:
</p>
<blockquote class="citation">
<pre class="wiki"> set(PI.Vrepresentation()) # optional - pynormaliz
</pre><p>
Question: I have "normaliz" in my optional installed packages but not "pynormaliz", is the above naming correct then?
</p>
</blockquote>
<p>
The only way that sage accesses normaliz is via pynormaliz, so this is correct.
</p>
TicketmoritzTue, 22 Aug 2017 07:14:36 GMTstatus changed
https://trac.sagemath.org/ticket/16045#comment:41
https://trac.sagemath.org/ticket/16045#comment:41
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<blockquote class="citation">
<p>
I am aware that this is not the topic of this ticket but since the tests failed here, it is probably best to treat this here.
</p>
</blockquote>
<p>
I disagree. This should not be treated here, but a new ticket should be opened. If we proceed as you propose (and everybody else does the same), this random pynormaliz bug will be treated in every ticket that is around.
</p>
<p>
In fact it already seems to be fixed here:
</p>
<p>
<a class="ext-link" href="https://trac.sagemath.org/ticket/23586"><span class="icon"></span>https://trac.sagemath.org/ticket/23586</a>
</p>
<p>
see also:
</p>
<p>
<a class="ext-link" href="https://trac.sagemath.org/ticket/23637"><span class="icon"></span>https://trac.sagemath.org/ticket/23637</a>
</p>
<p>
and
</p>
<p>
<a class="ext-link" href="https://git.sagemath.org/sage.git/diff?id2=effcedba414f8832b07e6e77cf0b4a6aed6aff9b&id=cb2fcfd6760f74db9dc16def7edfef00c96cf657"><span class="icon"></span>https://git.sagemath.org/sage.git/diff?id2=effcedba414f8832b07e6e77cf0b4a6aed6aff9b&id=cb2fcfd6760f74db9dc16def7edfef00c96cf657</a>
</p>
TicketjipilabTue, 22 Aug 2017 13:46:21 GMT
https://trac.sagemath.org/ticket/16045#comment:42
https://trac.sagemath.org/ticket/16045#comment:42
<blockquote class="citation">
<p>
The only way that sage accesses normaliz is via pynormaliz, so this is correct.
</p>
</blockquote>
<p>
My bad, I confused both and only installed normaliz. Oh well...
</p>
TicketjipilabTue, 22 Aug 2017 14:18:00 GMTbranch changed
https://trac.sagemath.org/ticket/16045#comment:43
https://trac.sagemath.org/ticket/16045#comment:43
<ul>
<li><strong>branch</strong>
changed from <em>u/moritz/16045</em> to <em>u/jipilab/16045</em>
</li>
</ul>
TicketjipilabTue, 22 Aug 2017 14:33:40 GMTstatus, commit, description changed
https://trac.sagemath.org/ticket/16045#comment:44
https://trac.sagemath.org/ticket/16045#comment:44
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>commit</strong>
changed from <em>fa46ceef2634458cd6dfc4146feb65f1945ea5a2</em> to <em>f5d47cf5576ca2f752aaac47f859b2c997535af3</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/16045?action=diff&version=44">diff</a>)
</li>
</ul>
<blockquote class="citation">
<p>
I disagree. This should not be treated here, but a new ticket should be opened. If we proceed as you propose (and everybody else does the same), this random pynormaliz bug will be treated in every ticket that is around.
</p>
<p>
In fact it already seems to be fixed here:
</p>
<p>
<a class="ext-link" href="https://trac.sagemath.org/ticket/23586"><span class="icon"></span>https://trac.sagemath.org/ticket/23586</a>
</p>
<p>
see also:
</p>
<p>
<a class="ext-link" href="https://trac.sagemath.org/ticket/23637"><span class="icon"></span>https://trac.sagemath.org/ticket/23637</a>
</p>
<p>
and
</p>
<p>
<a class="ext-link" href="https://git.sagemath.org/sage.git/diff?id2=effcedba414f8832b07e6e77cf0b4a6aed6aff9b&id=cb2fcfd6760f74db9dc16def7edfef00c96cf657"><span class="icon"></span>https://git.sagemath.org/sage.git/diff?id2=effcedba414f8832b07e6e77cf0b4a6aed6aff9b&id=cb2fcfd6760f74db9dc16def7edfef00c96cf657</a>
</p>
</blockquote>
<p>
All right, good to know, thanks for looking it up!
</p>
<p>
Should we add a dependancy in such cases, or perhaps just wait...?
</p>
<p>
I corrected two indentations. This looks good to me now, tests pass on my machine with pynormaliz (!).
</p>
<p>
I extended the description of the ticket a bit, if you believe it should contain some more information you can add it, otherwise, I'd it is ready to go.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=2b0fb6d6b72d2c63fbcca640a44d0a5b15013f13"><span class="icon"></span>2b0fb6d</a></td><td><code>Merge branch 'u/moritz/16045' of git://trac.sagemath.org/sage into 16045</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=f5d47cf5576ca2f752aaac47f859b2c997535af3"><span class="icon"></span>f5d47cf</a></td><td><code>Corrected some indentations</code>
</td></tr></table>
TicketmoritzTue, 22 Aug 2017 14:46:04 GMT
https://trac.sagemath.org/ticket/16045#comment:45
https://trac.sagemath.org/ticket/16045#comment:45
<p>
Thanks for the review, JP! I don't think we should put a dependency for the pynormaliz-set-thing.
</p>
TicketmoritzTue, 22 Aug 2017 20:37:41 GMTmilestone set
https://trac.sagemath.org/ticket/16045#comment:46
https://trac.sagemath.org/ticket/16045#comment:46
<ul>
<li><strong>milestone</strong>
set to <em>sage-8.1</em>
</li>
</ul>
TicketvbraunSun, 10 Sep 2017 11:56:41 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/16045#comment:47
https://trac.sagemath.org/ticket/16045#comment:47
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/jipilab/16045</em> to <em>f5d47cf5576ca2f752aaac47f859b2c997535af3</em>
</li>
</ul>
Ticket