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: sage-7.6
Component: geometry Keywords: days84, polytope
Cc: Jean-Philippe 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:

Status badges

Description (last modified by Marcelo Forets)

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 Vincent Delecroix

Dependencies: #22522
Description: modified (diff)

comment:2 Changed 6 years ago by Marcelo Forets

Branch: u/mforets/22497

comment:3 Changed 6 years ago by Marcelo Forets

Cc: Jean-Philippe Labbé added
Commit: 6a474f92580914f1cf42595fd8ee7b882b244b5d

New commits:

d5ff15422497: generic interface to LattE integrale count
96e4099Integral of a polynomial over a polytope.
d3c9589Add volume function to generic latte_int interface.
000bf8bRestructured the script, with an integrate function accepting different valuations.
5aa6695Added test for helper function _to_latte_polynomial.
72d03a1Minor changes to helper function and integrate.
6a474f9fixed a typo in the docstring

comment:4 Changed 6 years ago by git

Commit: 6a474f92580914f1cf42595fd8ee7b882b244b5d17911f7051d618046f8ed37681b6f4516ec751b3

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

17911f7Added integrate method to Polyhedron base.py

comment:5 Changed 6 years ago by Marcelo Forets

Description: modified (diff)

comment:6 Changed 6 years ago by git

Commit: 17911f7051d618046f8ed37681b6f4516ec751b3507aea5adb6f05ddc95cfef7cd79d24d3041de10

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

91d885eFix the docstrings, and enhance integrate method.
507aea5Add the new volume engine Polyhedron.

comment:7 Changed 6 years ago by Marcelo Forets

Status: newneeds_review

comment:8 Changed 6 years ago by Vincent Delecroix

Status: needs_reviewneeds_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 git

Commit: 507aea5adb6f05ddc95cfef7cd79d24d3041de10a563192b0dcbce9ab4e1387a1f3435e5d179cbc9

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

a563192fix a bug in _volume_latte

comment:10 Changed 6 years ago by Marcelo Forets

Branch: u/mforets/22497u/mforets/20887
Status: needs_workneeds_review

comment:11 Changed 6 years ago by git

Commit: a563192b0dcbce9ab4e1387a1f3435e5d179cbc99ac82796710a0dfd1b99d95addf78cdfc1b37652

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

9ac8279reject RDF, but add an example

comment:12 Changed 6 years ago by Marcelo Forets

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/sage-src/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 498, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/forets/sage-src/sage/local/lib/python2.7/site-packages/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/sage-src/sage/local/lib/python2.7/site-packages/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 Marcelo Forets

(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 Marcelo Forets

Authors: Marcelo Forets

comment:15 Changed 6 years ago by Matthias Köppe

+        Testing convex decomposition algorithm::

this should be "cone decomposition".

Polyhedron.integrate should include tests for lower-dimensional 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 Matthias Köppe

Milestone: sage-7.3sage-7.6
Reviewers: Matthias Koeppe
Status: needs_reviewneeds_work

comment:17 Changed 6 years ago by git

Commit: 9ac82796710a0dfd1b99d95addf78cdfc1b37652ec1589760e046f6cd18ead736b36338a18b84d74

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

ec15897add test for low-dim polytope and fix docstring typo

comment:18 Changed 6 years ago by Marcelo Forets

Status: needs_workneeds_review

comment:19 in reply to:  15 ; Changed 6 years ago by Marcelo Forets

Replying to mkoeppe:

+        Testing convex decomposition algorithm::

this should be "cone decomposition".

Polyhedron.integrate should include tests for lower-dimensional 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 full-dimensional, 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 low-dim 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 ; Changed 6 years ago by Matthias Köppe

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/6

and 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 6 years ago by Marcelo Forets

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/6

and 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 Moritz Firsching

Cc: Moritz Firsching added

comment:23 Changed 6 years ago by Matthias Köppe

Status: needs_reviewneeds_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/sage-rebasing/another-local-sans-autotools/lib/python2.7/site-packages/sage/doctest/forker.py", line 498, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/mkoeppe/s/sage/sage-rebasing/another-local-sans-autotools/lib/python2.7/site-packages/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/sage-rebasing/another-local-sans-autotools/lib/python2.7/site-packages/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 git

Commit: ec1589760e046f6cd18ead736b36338a18b84d741cf59f415161bb1901c0a1894fc9166dd0d90153

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

1cf59f4fix last doctest in integrate (exception mismatch)

comment:25 Changed 6 years ago by Marcelo Forets

Status: needs_workneeds_review

comment:26 in reply to:  23 Changed 6 years ago by Marcelo Forets

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/sage-rebasing/another-local-sans-autotools/lib/python2.7/site-packages/sage/doctest/forker.py", line 498, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/mkoeppe/s/sage/sage-rebasing/another-local-sans-autotools/lib/python2.7/site-packages/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/sage-rebasing/another-local-sans-autotools/lib/python2.7/site-packages/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 Marcelo Forets

Keywords: days84 polytope added

comment:28 Changed 6 years ago by Matthias Köppe

Status: needs_reviewpositive_review

comment:29 Changed 6 years ago by François Bissey

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 Volker Braun

Status: positive_reviewneeds_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 full-dimensional.
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/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/site-packages/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/site-packages/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 François Bissey

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 git

Commit: 1cf59f415161bb1901c0a1894fc9166dd0d90153dc544fac24882973b51a5e6c8c645ace92da1dd0

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

dc544fafix optional tag in integrate test

comment:33 Changed 6 years ago by Marcelo Forets

Status: needs_workneeds_review

comment:34 Changed 6 years ago by Matthias Köppe

Doesn't fbissey's comment regarding is_package_installed need addressing?

comment:35 Changed 6 years ago by François Bissey

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 6 years ago by Marcelo Forets

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 François Bissey

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 Matthias Köppe

Status: needs_reviewpositive_review

Ah, thanks for the clarification.

comment:39 Changed 6 years ago by Volker Braun

Branch: u/mforets/20887dc544fac24882973b51a5e6c8c645ace92da1dd0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.