Opened 5 years ago

Closed 4 years ago

#20887 closed enhancement (fixed)

Integration of polynomials over polytopes with LattE

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.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) Commit: dc544fac24882973b51a5e6c8c645ace92da1dd0
Dependencies: #22522 Stopgaps:

Description (last modified by mforets)

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 4 years ago by vdelecroix

  • Dependencies set to #22522
  • Description modified (diff)

comment:2 Changed 4 years ago by mforets

  • Branch set to u/mforets/22497

comment:3 Changed 4 years ago by mforets

  • Cc jipilab added
  • Commit set to 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 4 years ago by git

  • Commit changed from 6a474f92580914f1cf42595fd8ee7b882b244b5d to 17911f7051d618046f8ed37681b6f4516ec751b3

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

17911f7Added integrate method to Polyhedron base.py

comment:5 Changed 4 years ago by mforets

  • Description modified (diff)

comment:6 Changed 4 years ago by git

  • Commit changed from 17911f7051d618046f8ed37681b6f4516ec751b3 to 507aea5adb6f05ddc95cfef7cd79d24d3041de10

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 4 years ago by mforets

  • Status changed from new to needs_review

comment:8 Changed 4 years ago by vdelecroix

  • 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 4 years ago by git

  • Commit changed from 507aea5adb6f05ddc95cfef7cd79d24d3041de10 to a563192b0dcbce9ab4e1387a1f3435e5d179cbc9

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

a563192fix a bug in _volume_latte

comment:10 Changed 4 years ago by mforets

  • Branch changed from u/mforets/22497 to u/mforets/20887
  • Status changed from needs_work to needs_review

comment:11 Changed 4 years ago by git

  • Commit changed from a563192b0dcbce9ab4e1387a1f3435e5d179cbc9 to 9ac82796710a0dfd1b99d95addf78cdfc1b37652

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

9ac8279reject RDF, but add an example

comment:12 Changed 4 years ago by mforets

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 4 years ago by mforets

(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 4 years ago by mforets

  • Authors set to Marcelo Forets

comment:15 follow-up: Changed 4 years ago by 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.

comment:16 Changed 4 years ago by mkoeppe

  • Milestone changed from sage-7.3 to sage-7.6
  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to needs_work

comment:17 Changed 4 years ago by git

  • Commit changed from 9ac82796710a0dfd1b99d95addf78cdfc1b37652 to ec1589760e046f6cd18ead736b36338a18b84d74

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

ec15897add test for low-dim polytope and fix docstring typo

comment:18 Changed 4 years ago by mforets

  • Status changed from needs_work to needs_review

comment:19 in reply to: ↑ 15 ; follow-up: Changed 4 years ago by mforets

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 ; follow-up: Changed 4 years ago by 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.

comment:21 in reply to: ↑ 20 Changed 4 years ago by mforets

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 4 years ago by moritz

  • Cc moritz added

comment:23 follow-up: Changed 4 years ago by mkoeppe

  • 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/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 4 years ago by git

  • Commit changed from ec1589760e046f6cd18ead736b36338a18b84d74 to 1cf59f415161bb1901c0a1894fc9166dd0d90153

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

1cf59f4fix last doctest in integrate (exception mismatch)

comment:25 Changed 4 years ago by mforets

  • Status changed from needs_work to needs_review

comment:26 in reply to: ↑ 23 Changed 4 years ago by mforets

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 4 years ago by mforets

  • Keywords days84 polytope added

comment:28 Changed 4 years ago by mkoeppe

  • Status changed from needs_review to positive_review

comment:29 Changed 4 years ago by fbissey

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 4 years ago by vbraun

  • 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 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 4 years ago by fbissey

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 4 years ago by git

  • Commit changed from 1cf59f415161bb1901c0a1894fc9166dd0d90153 to dc544fac24882973b51a5e6c8c645ace92da1dd0

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

dc544fafix optional tag in integrate test

comment:33 Changed 4 years ago by mforets

  • Status changed from needs_work to needs_review

comment:34 follow-up: Changed 4 years ago by mkoeppe

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

comment:35 Changed 4 years ago by fbissey

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 4 years ago by mforets

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 4 years ago by fbissey

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 4 years ago by mkoeppe

  • Status changed from needs_review to positive_review

Ah, thanks for the clarification.

comment:39 Changed 4 years ago by vbraun

  • Branch changed from u/mforets/20887 to dc544fac24882973b51a5e6c8c645ace92da1dd0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.