#20885 closed enhancement (fixed)
Normaliz/PyNormaliz interface: Fast backend for polyhedra, integral_points, integral_hull
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  geometry  Keywords:  
Cc:  tscrim, dimpase, yzh, novoselt, Winfried, nthiery, vdelecroix, moritz, jipilab, mmasdeu  Merged in:  
Authors:  Matthias Koeppe  Reviewers:  Travis Scrimshaw, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  6f58384 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
Normaliz is an excellent library for computations in affine monoids, vector configurations, lattice polytopes, and rational cones. There's a commandline program and a library (libnormaliz).
We already have normaliz as an optional package. This ticket:
 makes a shared library build of normaliz (using the new autotools build system of normaliz)
 adds the PyNormaliz package
 adds a Polyhedron_normaliz class (requested using backend='normaliz')
 ... which has fast implementations of
Polyhedron.integral_points()
(cf. #18029),Polyhedron.integral_hull()
To install both, put the upstream archives:
 https://github.com/Normaliz/Normaliz/releases/download/v3.1.4/normaliz3.1.4.tar.gz
 https://pypi.python.org/packages/8b/d3/46d35aa05d8d1b82c24d0e37905f9df7fed17ae41b78623e1d253c2f3b15/PyNormaliz1.0.tar.gz#md5=27a5f7d3fa0d96766d4f811495b0f5ce
into upstream/
and then use:
./sage f pynormaliz
See the examples in the Polyhedron_normaliz
documentation.
On followup tickets, should:
 provide fast implementations of existing methods of Polyhedron, Cone, triangulations, ...
 provide new methods for Normaliz's additional features.
Adding these methods would not require Cython programming and would happen on several separate tickets. All it takes is reading the Normaliz manual
Change History (43)
comment:1 Changed 5 years ago by
 Cc tscrim added
 Description modified (diff)
comment:2 Changed 5 years ago by
 Cc dimpase added
 Description modified (diff)
 Type changed from task to enhancement
comment:3 Changed 5 years ago by
 Description modified (diff)
comment:4 Changed 5 years ago by
 Branch set to u/mkoeppe/normaliz_interface
comment:5 Changed 5 years ago by
 Commit set to 8881612b46c5948cd305fd8e3ad56fb487478991
 Description modified (diff)
comment:6 Changed 5 years ago by
 Cc yzh added
comment:7 Changed 5 years ago by
 Commit changed from 8881612b46c5948cd305fd8e3ad56fb487478991 to 1e9140313eb2fbc1dcc35f0d47023085a8f66f9e
comment:8 Changed 5 years ago by
 Description modified (diff)
 Milestone changed from sage7.3 to sage7.5
comment:9 Changed 5 years ago by
 Commit changed from 1e9140313eb2fbc1dcc35f0d47023085a8f66f9e to 1786d6feebef05fb460c06f38adba802ed8ae7a2
comment:10 Changed 5 years ago by
 Description modified (diff)
 Summary changed from Normaliz interface to Normaliz/PyNormaliz interface
comment:11 Changed 5 years ago by
 Description modified (diff)
comment:12 Changed 5 years ago by
 Cc novoselt added
comment:13 Changed 5 years ago by
comment:14 Changed 5 years ago by
 Commit changed from 1786d6feebef05fb460c06f38adba802ed8ae7a2 to bf94a59479dee74b0dca2284ed61fecdf6ead039
Branch pushed to git repo; I updated commit sha1. New commits:
bf94a59  Update license info

comment:15 Changed 5 years ago by
 Description modified (diff)
comment:16 Changed 5 years ago by
 Cc Winfried added
comment:17 Changed 5 years ago by
 Commit changed from bf94a59479dee74b0dca2284ed61fecdf6ead039 to 84af739b3e86988e1c7b3dc39a1269b59e7702cb
comment:18 Changed 5 years ago by
 Commit changed from 84af739b3e86988e1c7b3dc39a1269b59e7702cb to 8cfe6c07ac38084309ec055587ea1019d02f5c06
Branch pushed to git repo; I updated commit sha1. New commits:
8cfe6c0  Polyhedron_normaliz: Implement

comment:19 Changed 5 years ago by
 Commit changed from 8cfe6c07ac38084309ec055587ea1019d02f5c06 to ea9e8f625e955dd46357e50dbbca77b1eaa7f844
Branch pushed to git repo; I updated commit sha1. New commits:
ea9e8f6  MixedIntegerLinearProgram.polyhedron: Actually pass on **kwds

comment:20 Changed 5 years ago by
 Commit changed from ea9e8f625e955dd46357e50dbbca77b1eaa7f844 to f27035b185a79f4de786deab83c24d83ec49d791
comment:21 Changed 5 years ago by
 Cc nthiery added
 Summary changed from Normaliz/PyNormaliz interface to Normaliz/PyNormaliz interface: Fast backend for polyhedra, integral_points
comment:22 Changed 5 years ago by
 Commit changed from f27035b185a79f4de786deab83c24d83ec49d791 to 099179745f56a2ed0957ada787826fc9336cc73a
Branch pushed to git repo; I updated commit sha1. New commits:
0991797  Polyhedron_normaliz.integral_points(): Fast path for small bounding boxes

comment:23 followup: ↓ 25 Changed 5 years ago by
Why did you remove the content of SPKG.txt (commit 5e87434
)?
comment:24 followup: ↓ 26 Changed 5 years ago by
Why don't you provide a package for pynormaliz? Downloading a nonspecified version from github looks sloppy to me.
comment:25 in reply to: ↑ 23 Changed 5 years ago by
Replying to vdelecroix:
Why did you remove the content of SPKG.txt (commit
5e87434
)?
I've removed information that no longer applies and removed the change log because to my understanding we no longer do change logs but rather rely on git history for packages.
comment:26 in reply to: ↑ 24 Changed 5 years ago by
Replying to vdelecroix:
Why don't you provide a package for pynormaliz? Downloading a nonspecified version from github looks sloppy to me.
Yes, will do when it has stabilized.
comment:27 Changed 5 years ago by
 Commit changed from 099179745f56a2ed0957ada787826fc9336cc73a to 6629dc3c1bdeebca7b09ef2f8f99510449ecff56
Branch pushed to git repo; I updated commit sha1. New commits:
6629dc3  Polyhedron.integral_hull: New

comment:28 Changed 5 years ago by
 Summary changed from Normaliz/PyNormaliz interface: Fast backend for polyhedra, integral_points to Normaliz/PyNormaliz interface: Fast backend for polyhedra, integral_points, integral_hull
comment:29 Changed 5 years ago by
 Commit changed from 6629dc3c1bdeebca7b09ef2f8f99510449ecff56 to 44271f86454131ec80f5b7e4ae1f43bddfee75e6
Branch pushed to git repo; I updated commit sha1. New commits:
44271f8  Polyhedron_normaliz: Handle empty polyhedra

comment:30 Changed 5 years ago by
 Commit changed from 44271f86454131ec80f5b7e4ae1f43bddfee75e6 to 9737e99d272b6d64cea1138d5cca1204fb7a4f67
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c23bd8d  Use autotoolized normaliz, official release 3.1.3

78dd42e  Preliminary pynormaliz package

6b07dee  Add stubs for Polyhedron_normaliz

d45aedf  Polyhedron_normaliz: Implement

942ca7b  MixedIntegerLinearProgram.polyhedron: Actually pass on **kwds

dc7289a  Polyhedron_normaliz.integer_points: Implement

1a5e330  Polyhedron_normaliz.integral_points(): Fast path for small bounding boxes

2975534  Polyhedron.integral_hull: New

d790c15  Polyhedron_normaliz: Handle empty polyhedra

9737e99  Update normaliz to 3.1.4

comment:31 Changed 5 years ago by
 Description modified (diff)
comment:32 Changed 5 years ago by
 Description modified (diff)
comment:33 Changed 5 years ago by
 Commit changed from 9737e99d272b6d64cea1138d5cca1204fb7a4f67 to 5e6d972186762ee94b3fff60b0d78ea727128935
comment:34 Changed 5 years ago by
 Cc vdelecroix moritz jipilab mmasdeu added
 Status changed from new to needs_review
comment:35 Changed 5 years ago by
 Branch changed from u/mkoeppe/normaliz_interface to public/geometry/normaliz_interface20885
 Commit changed from 5e6d972186762ee94b3fff60b0d78ea727128935 to 6f583841aa771839f9ecbcb8186e34cad07fa014
 Reviewers set to Travis Scrimshaw
I was able to install everything without problems and run some examples (such as my E_{8} polytope, which runs in under 150ms compared to 12+s without this interface). I made some reviewer changes to the documentation. The setup for the spkgs LGTM. I'm willing to set a positive review, provided my changes are good, but I would appreciate if someone else looked over the packaging side of things.
New commits:
6f58384  Some reviewer changes and tweaks.

comment:36 Changed 5 years ago by
These changes are fine with me.
comment:37 Changed 5 years ago by
All the info regarding how to create the Sage package from the sources seems to be gone now. Can it be put back (suitably updated)?
comment:38 Changed 5 years ago by
It's using the upstream distributions. No repackaging involved.
comment:40 Changed 5 years ago by
 Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Dima Pasechnik
comment:41 Changed 5 years ago by
 Branch changed from public/geometry/normaliz_interface20885 to 6f583841aa771839f9ecbcb8186e34cad07fa014
 Resolution set to fixed
 Status changed from positive_review to closed
comment:42 Changed 5 years ago by
 Commit 6f583841aa771839f9ecbcb8186e34cad07fa014 deleted
Something looks like wrong
https://groups.google.com/forum/#!topic/sagedevel/IMlNMe5Xk5A
comment:43 Changed 5 years ago by
I've created #22093 for this
New commits:
Use autotoolized normaliz