Opened 6 years ago
Closed 6 years ago
#20887 closed enhancement (fixed)
Integration of polynomials over polytopes with LattE
Reported by:  Matthias Köppe  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  geometry  Keywords:  days84, polytope 
Cc:  JeanPhilippe Labbé, Moritz Firsching  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 6 years ago by
Dependencies:  → #22522 

Description:  modified (diff) 
comment:2 Changed 6 years ago by
Branch:  → u/mforets/22497 

comment:3 Changed 6 years ago by
Cc:  JeanPhilippe Labbé added 

Commit:  → 6a474f92580914f1cf42595fd8ee7b882b244b5d 
comment:4 Changed 6 years ago by
Commit:  6a474f92580914f1cf42595fd8ee7b882b244b5d → 17911f7051d618046f8ed37681b6f4516ec751b3 

Branch pushed to git repo; I updated commit sha1. New commits:
17911f7  Added integrate method to Polyhedron base.py

comment:5 Changed 6 years ago by
Description:  modified (diff) 

comment:6 Changed 6 years ago by
Commit:  17911f7051d618046f8ed37681b6f4516ec751b3 → 507aea5adb6f05ddc95cfef7cd79d24d3041de10 

comment:7 Changed 6 years ago by
Status:  new → needs_review 

comment:8 Changed 6 years ago by
Status:  needs_review → 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 6 years ago by
Commit:  507aea5adb6f05ddc95cfef7cd79d24d3041de10 → a563192b0dcbce9ab4e1387a1f3435e5d179cbc9 

Branch pushed to git repo; I updated commit sha1. New commits:
a563192  fix a bug in _volume_latte

comment:10 Changed 6 years ago by
Branch:  u/mforets/22497 → u/mforets/20887 

Status:  needs_work → needs_review 
comment:11 Changed 6 years ago by
Commit:  a563192b0dcbce9ab4e1387a1f3435e5d179cbc9 → 9ac82796710a0dfd1b99d95addf78cdfc1b37652 

Branch pushed to git repo; I updated commit sha1. New commits:
9ac8279  reject RDF, but add an example

comment:12 Changed 6 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 6 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 6 years ago by
Authors:  → Marcelo Forets 

comment:15 followup: 19 Changed 6 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 6 years ago by
Milestone:  sage7.3 → sage7.6 

Reviewers:  → Matthias Koeppe 
Status:  needs_review → needs_work 
comment:17 Changed 6 years ago by
Commit:  9ac82796710a0dfd1b99d95addf78cdfc1b37652 → 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 6 years ago by
Status:  needs_work → needs_review 

comment:19 followup: 20 Changed 6 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 followup: 21 Changed 6 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 Changed 6 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 6 years ago by
Cc:  Moritz Firsching added 

comment:23 followup: 26 Changed 6 years ago by
Status:  needs_review → 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 6 years ago by
Commit:  ec1589760e046f6cd18ead736b36338a18b84d74 → 1cf59f415161bb1901c0a1894fc9166dd0d90153 

Branch pushed to git repo; I updated commit sha1. New commits:
1cf59f4  fix last doctest in integrate (exception mismatch)

comment:25 Changed 6 years ago by
Status:  needs_work → needs_review 

comment:26 Changed 6 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 6 years ago by
Keywords:  days84 polytope added 

comment:28 Changed 6 years ago by
Status:  needs_review → positive_review 

comment:29 Changed 6 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 6 years ago by
Status:  positive_review → 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 6 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 6 years ago by
Commit:  1cf59f415161bb1901c0a1894fc9166dd0d90153 → dc544fac24882973b51a5e6c8c645ace92da1dd0 

Branch pushed to git repo; I updated commit sha1. New commits:
dc544fa  fix optional tag in integrate test

comment:33 Changed 6 years ago by
Status:  needs_work → needs_review 

comment:34 followup: 36 Changed 6 years ago by
Doesn't fbissey's comment regarding is_package_installed
need addressing?
comment:35 Changed 6 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 Changed 6 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 6 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 6 years ago by
Status:  needs_review → positive_review 

Ah, thanks for the clarification.
comment:39 Changed 6 years ago by
Branch:  u/mforets/20887 → dc544fac24882973b51a5e6c8c645ace92da1dd0 

Resolution:  → fixed 
Status:  positive_review → 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