Opened 6 years ago
Closed 5 years ago
#20887 closed enhancement (fixed)
Integration of polynomials over polytopes with LattE
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  geometry  Keywords:  days84, polytope 
Cc:  jipilab, moritz  Merged in:  
Authors:  Marcelo Forets  Reviewers:  Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  dc544fa (Commits, GitHub, GitLab)  Commit:  dc544fac24882973b51a5e6c8c645ace92da1dd0 
Dependencies:  #22522  Stopgaps: 
Description (last modified by )
The ticket #22522 makes available a function sage.interfaces.latte.integrate
that calls the corresponding LattE function. We make this low level function available as a method of polyhedra.
Moreover, we add a new "engine" to the existent volume
method of Polyhedron, interfacing with sage.interfaces.latte.integrate
.
Change History (39)
comment:1 Changed 5 years ago by
 Dependencies set to #22522
 Description modified (diff)
comment:2 Changed 5 years ago by
 Branch set to u/mforets/22497
comment:3 Changed 5 years ago by
 Cc jipilab added
 Commit set to 6a474f92580914f1cf42595fd8ee7b882b244b5d
comment:4 Changed 5 years ago by
 Commit changed from 6a474f92580914f1cf42595fd8ee7b882b244b5d to 17911f7051d618046f8ed37681b6f4516ec751b3
Branch pushed to git repo; I updated commit sha1. New commits:
17911f7  Added integrate method to Polyhedron base.py

comment:5 Changed 5 years ago by
 Description modified (diff)
comment:6 Changed 5 years ago by
 Commit changed from 17911f7051d618046f8ed37681b6f4516ec751b3 to 507aea5adb6f05ddc95cfef7cd79d24d3041de10
comment:7 Changed 5 years ago by
 Status changed from new to needs_review
comment:8 Changed 5 years ago by
 Status changed from needs_review to needs_work
The commits here and at #22522 are exactly the same (last being 507aea5
). You need to be clear about what belong to which ticket and update the branches accordingly.
comment:9 Changed 5 years ago by
 Commit changed from 507aea5adb6f05ddc95cfef7cd79d24d3041de10 to a563192b0dcbce9ab4e1387a1f3435e5d179cbc9
Branch pushed to git repo; I updated commit sha1. New commits:
a563192  fix a bug in _volume_latte

comment:10 Changed 5 years ago by
 Branch changed from u/mforets/22497 to u/mforets/20887
 Status changed from needs_work to needs_review
comment:11 Changed 5 years ago by
 Commit changed from a563192b0dcbce9ab4e1387a1f3435e5d179cbc9 to 9ac82796710a0dfd1b99d95addf78cdfc1b37652
Branch pushed to git repo; I updated commit sha1. New commits:
9ac8279  reject RDF, but add an example

comment:12 Changed 5 years ago by
there is a test that's being incorrectly parsed by the bot (in the shell it's fine):
********************************************************************** File "src/sage/geometry/polyhedron/base.py", line 4101, in sage.geometry.polyhedron.base.Polyhedron_base.integrate Failed example: P.integrate('[[1,[2,2]]]') # optional  latte_int Expected: Traceback (most recent call last): ... TypeError: LattE integrale cannot be applied over inexact rings. Got: <BLANKLINE> Traceback (most recent call last): File "/Users/forets/sagesrc/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 498, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/forets/sagesrc/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 861, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.integrate[15]>", line 1, in <module> P.integrate('[[1,[2,2]]]') # optional  latte_int File "/Users/forets/sagesrc/sage/local/lib/python2.7/sitepackages/sage/geometry/polyhedron/base.py", line 4109, in integrate raise ValueError("LattE integrale cannot be applied over inexact rings.") ValueError: LattE integrale cannot be applied over inexact rings. **********************************************************************
comment:13 Changed 5 years ago by
(migrated from #22522)
Replying to mkoeppe:
Integration over an RDF polyhedron via QQ polyhedron (latte) could make sense as long as the method converts the answer back to RDF to indicate that the answer is inexact.
Ok, that makes sense! Moreover Vincent convinced me that coercing and instantiating like that is a bad idea, potentially very costly and because it's hidden. In the new patch that's been reverted, but an illustrative example was added.
As to
change_ring
, this could be useful. I had related discussions with JP.
I've created #22574 for change_ring and #22575 for change_backend.
comment:14 Changed 5 years ago by
comment:15 followup: ↓ 19 Changed 5 years ago by
+ Testing convex decomposition algorithm::
this should be "cone decomposition".
Polyhedron.integrate
should include tests for lowerdimensional polytopes. Those are not supported by latte's integrate. The result should either be 0  or a proper error should be raised.
comment:16 Changed 5 years ago by
 Milestone changed from sage7.3 to sage7.6
 Reviewers set to Matthias Koeppe
 Status changed from needs_review to needs_work
comment:17 Changed 5 years ago by
 Commit changed from 9ac82796710a0dfd1b99d95addf78cdfc1b37652 to ec1589760e046f6cd18ead736b36338a18b84d74
Branch pushed to git repo; I updated commit sha1. New commits:
ec15897  add test for lowdim polytope and fix docstring typo

comment:18 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:19 in reply to: ↑ 15 ; followup: ↓ 20 Changed 5 years ago by
Replying to mkoeppe:
+ Testing convex decomposition algorithm::this should be "cone decomposition".
Polyhedron.integrate
should include tests for lowerdimensional polytopes. Those are not supported by latte's integrate. The result should either be 0  or a proper error should be raised.
wait a moment, because i may have misunderstood:
1 if the polytope is not fulldimensional, but the polynomial is in low dimension, then latte gives an answer wrt to the relative interior, as in:
sage: P = Polyhedron(vertices=[[0,0],[1,1]]) sage: from sage.interfaces.latte import integrate as integrate sage: x = polygen(QQ, 'x') sage: integrate(P.cdd_Hrepresentation(), 2*x^2 + x  1, cdd=True) 1/6
and we should keep this behaviour.
2 however, in the situation of a multivariate polynomial in a lowdim polytope it breaks,
sage: P = Polyhedron(vertices=[[0,0],[1,1]]) sage: from sage.interfaces.latte import integrate as integrate sage: x, y = polygens(QQ, 'x, y') sage: integrate(P.cdd_Hrepresentation(), 2*x^2 + x  y, cdd=True) ... SetLength: can't change this vector's length
and we should raise an exception.
can you confirm?
comment:20 in reply to: ↑ 19 ; followup: ↓ 21 Changed 5 years ago by
Replying to mforets:
sage: P = Polyhedron(vertices=[[0,0],[1,1]]) sage: from sage.interfaces.latte import integrate as integrate sage: x = polygen(QQ, 'x') sage: integrate(P.cdd_Hrepresentation(), 2*x^2 + x  1, cdd=True) 1/6and we should keep this behaviour.
Unfortunately, there is no control over what exact transformation LattE applies; and so the input polynomial is meaningless even though it has the correct number of variables.
comment:21 in reply to: ↑ 20 Changed 5 years ago by
Replying to mkoeppe:
Replying to mforets:
sage: P = Polyhedron(vertices=[[0,0],[1,1]]) sage: from sage.interfaces.latte import integrate as integrate sage: x = polygen(QQ, 'x') sage: integrate(P.cdd_Hrepresentation(), 2*x^2 + x  1, cdd=True) 1/6and we should keep this behaviour.
Unfortunately, there is no control over what exact transformation LattE applies; and so the input polynomial is meaningless even though it has the correct number of variables.
ok then; commit ec15897 raises exception in both cases.
comment:22 Changed 5 years ago by
 Cc moritz added
comment:23 followup: ↓ 26 Changed 5 years ago by
 Status changed from needs_review to needs_work
I tested this on top of 7.6rc0 and got:
sage t src/sage/geometry/polyhedron/base.py ********************************************************************** File "src/sage/geometry/polyhedron/base.py", line 4232, in sage.geometry.polyhedron.base.Polyhedron_base.integrate Failed example: P.integrate('[[1,[2,2]]]') # optional  latte_int Expected: Traceback (most recent call last): ... TypeError: LattE integrale cannot be applied over inexact rings. Got: <BLANKLINE> Traceback (most recent call last): File "/Users/mkoeppe/s/sage/sagerebasing/anotherlocalsansautotools/lib/python2.7/sitepackages/sage/doctest/forker.py", line 498, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/mkoeppe/s/sage/sagerebasing/anotherlocalsansautotools/lib/python2.7/sitepackages/sage/doctest/forker.py", line 861, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.integrate[18]>", line 1, in <module> P.integrate('[[1,[2,2]]]') # optional  latte_int File "/Users/mkoeppe/s/sage/sagerebasing/anotherlocalsansautotools/lib/python2.7/sitepackages/sage/geometry/polyhedron/base.py", line 4240, in integrate raise ValueError("LattE integrale cannot be applied over inexact rings.") ValueError: LattE integrale cannot be applied over inexact rings. **********************************************************************
comment:24 Changed 5 years ago by
 Commit changed from ec1589760e046f6cd18ead736b36338a18b84d74 to 1cf59f415161bb1901c0a1894fc9166dd0d90153
Branch pushed to git repo; I updated commit sha1. New commits:
1cf59f4  fix last doctest in integrate (exception mismatch)

comment:25 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:26 in reply to: ↑ 23 Changed 5 years ago by
Replying to mkoeppe:
I tested this on top of 7.6rc0 and got:
sage t src/sage/geometry/polyhedron/base.py ********************************************************************** File "src/sage/geometry/polyhedron/base.py", line 4232, in sage.geometry.polyhedron.base.Polyhedron_base.integrate Failed example: P.integrate('[[1,[2,2]]]') # optional  latte_int Expected: Traceback (most recent call last): ... TypeError: LattE integrale cannot be applied over inexact rings. Got: <BLANKLINE> Traceback (most recent call last): File "/Users/mkoeppe/s/sage/sagerebasing/anotherlocalsansautotools/lib/python2.7/sitepackages/sage/doctest/forker.py", line 498, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/mkoeppe/s/sage/sagerebasing/anotherlocalsansautotools/lib/python2.7/sitepackages/sage/doctest/forker.py", line 861, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.integrate[18]>", line 1, in <module> P.integrate('[[1,[2,2]]]') # optional  latte_int File "/Users/mkoeppe/s/sage/sagerebasing/anotherlocalsansautotools/lib/python2.7/sitepackages/sage/geometry/polyhedron/base.py", line 4240, in integrate raise ValueError("LattE integrale cannot be applied over inexact rings.") ValueError: LattE integrale cannot be applied over inexact rings. **********************************************************************
thanks Matthias; i did run the tests before submitting, but there was this "<BLANKLINE>" thing that i didn't know how to solve. but actually it was a trivial error on my side. anyway, commit 1cf59f4 shall fix it.
comment:27 Changed 5 years ago by
 Keywords days84 polytope added
comment:28 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:29 Changed 5 years ago by
I have to ask, at no point are importing is_package_installed
from sage.misc.package
or sage.misc.all
, yet you are using it. How it is that you don't get "global name is_package_installed
is not defined"?
comment:30 Changed 5 years ago by
 Status changed from positive_review to needs_work
sage t long src/sage/geometry/polyhedron/base.py ********************************************************************** File "src/sage/geometry/polyhedron/base.py", line 4308, in sage.geometry.polyhedron.base.Polyhedron_base.integrate Failed example: P.integrate(x*y) Expected: Traceback (most recent call last): ... NotImplementedError: The polytope must be fulldimensional. Got: <BLANKLINE> Traceback (most recent call last): File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 498, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 861, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.integrate[6]>", line 1, in <module> P.integrate(x*y) File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/geometry/polyhedron/base.py", line 4355, in integrate raise NotImplementedError('You must install the optional latte_int package for this function to work.') NotImplementedError: You must install the optional latte_int package for this function to work. **********************************************************************
comment:31 Changed 5 years ago by
I should have thought about that! Never mind "is_package_installed", it is only visible at all because you forgot to mark that particular test #optional  latte_int
.
comment:32 Changed 5 years ago by
 Commit changed from 1cf59f415161bb1901c0a1894fc9166dd0d90153 to dc544fac24882973b51a5e6c8c645ace92da1dd0
Branch pushed to git repo; I updated commit sha1. New commits:
dc544fa  fix optional tag in integrate test

comment:33 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:34 followup: ↓ 36 Changed 5 years ago by
Doesn't fbissey's comment regarding is_package_installed
need addressing?
comment:35 Changed 5 years ago by
It's a funny, it has to work due to a chain of import from all.py
from sage.misc.all import * # takes a while
and in misc/all.py
from .package import (installed_packages, is_package_installed, standard_packages, optional_packages, experimental_packages, package_versions)
But most other call to it, do an explicit import. I would think it is supposed to work unless I am missing something.
comment:36 in reply to: ↑ 34 Changed 5 years ago by
Replying to mkoeppe:
Doesn't fbissey's comment regarding
is_package_installed
need addressing?
but is_package_installed
is imported above (line 25). it also has to be imported in the function body? thanks.
comment:37 Changed 5 years ago by
Let's call it a "user" error and forget about my comment about it. I have stuff from the feature branch which removes it. I didn't notice that this file was touched by it. That's why it is absent on my stuff.
comment:38 Changed 5 years ago by
 Status changed from needs_review to positive_review
Ah, thanks for the clarification.
comment:39 Changed 5 years ago by
 Branch changed from u/mforets/20887 to dc544fac24882973b51a5e6c8c645ace92da1dd0
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
22497: generic interface to LattE integrale count
Integral of a polynomial over a polytope.
Add volume function to generic latte_int interface.
Restructured the script, with an integrate function accepting different valuations.
Added test for helper function _to_latte_polynomial.
Minor changes to helper function and integrate.
fixed a typo in the docstring