Integration of polynomials over polytopes with LattE

[mkoeppe]

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.

Depends on #22522

CC: @jplab @mo271

Component: geometry

Keywords: days84, polytope

Author: Marcelo Forets

Branch/Commit: dc544fa

Reviewer: Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/20887

[videlec]

Dependencies: #22522

[mforets]

Branch: u/mforets/22497

[mforets]

Commit: 6a474f9

[mforets]

New commits:

d5ff154	22497: generic interface to LattE integrale count
96e4099	Integral of a polynomial over a polytope.
d3c9589	Add volume function to generic latte_int interface.
000bf8b	Restructured the script, with an integrate function accepting different valuations.
5aa6695	Added test for helper function _to_latte_polynomial.
72d03a1	Minor changes to helper function and integrate.
6a474f9	fixed a typo in the docstring

[sagetrac-git]

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

17911f7

Added integrate method to Polyhedron base.py

[sagetrac-git]

Changed commit from 6a474f9 to 17911f7

[sagetrac-git]

Changed commit from 17911f7 to 507aea5

[sagetrac-git]

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

91d885e	Fix the docstrings, and enhance integrate method.
507aea5	Add the new volume engine Polyhedron.

[videlec]

comment:8

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.

[sagetrac-git]

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

a563192

fix a bug in _volume_latte

[sagetrac-git]

Changed commit from 507aea5 to a563192

[mforets]

Changed branch from u/mforets/22497 to u/mforets/20887

[sagetrac-git]

Changed commit from a563192 to 9ac8279

[sagetrac-git]

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

9ac8279

reject RDF, but add an example

[mforets]

comment:12

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.
**********************************************************************

[mforets]

comment:13

(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.

[mforets]

Author: Marcelo Forets

[mkoeppe]

comment:15

+        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.

[mkoeppe]

Reviewer: Matthias Koeppe

[sagetrac-git]

Changed commit from ec15897 to 1cf59f4

[sagetrac-git]

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

1cf59f4

fix last doctest in integrate (exception mismatch)

[mforets]

comment:26

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 "" 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.

[mforets]

Changed keywords from none to days84, polytope

[kiwifb]

comment:29

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"?

[vbraun]

comment:30

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.
**********************************************************************

[kiwifb]

comment:31

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.

[sagetrac-git]

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

dc544fa

fix optional tag in integrate test

[sagetrac-git]

Changed commit from 1cf59f4 to dc544fa

[mkoeppe]

comment:34

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

[kiwifb]

comment:35

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.

[mforets]

comment:36

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.

[kiwifb]

comment:37

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.

[mkoeppe]

comment:38

Ah, thanks for the clarification.

[vbraun]

Changed branch from u/mforets/20887 to dc544fa