Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#20885 closed enhancement (fixed)

Normaliz/PyNormaliz interface: Fast backend for polyhedra, integral_points, integral_hull

Reported by: Matthias Köppe Owned by:
Priority: major Milestone: sage-7.5
Component: geometry Keywords:
Cc: Travis Scrimshaw, Dima Pasechnik, Yuan Zhou, Andrey Novoseltsev, Winfried Bruns, Nicolas M. Thiéry, Vincent Delecroix, Moritz Firsching, Jean-Philippe Labbé, Marc Masdeu Merged in:
Authors: Matthias Koeppe Reviewers: Travis Scrimshaw, Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 6f58384 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Matthias Köppe)

Normaliz is an excellent library for computations in affine monoids, vector configurations, lattice polytopes, and rational cones. There's a command-line 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:

into upstream/ and then use:

   ./sage -f pynormaliz

See the examples in the Polyhedron_normaliz documentation.

On follow-up 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 6 years ago by Matthias Köppe

Cc: Travis Scrimshaw added
Description: modified (diff)

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

Cc: Dima Pasechnik added
Description: modified (diff)
Type: taskenhancement

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

Description: modified (diff)

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

Branch: u/mkoeppe/normaliz_interface

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

Commit: 8881612b46c5948cd305fd8e3ad56fb487478991
Description: modified (diff)

New commits:

8881612Use autotoolized normaliz

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

Cc: Yuan Zhou added

comment:7 Changed 6 years ago by git

Commit: 8881612b46c5948cd305fd8e3ad56fb4874789911e9140313eb2fbc1dcc35f0d47023085a8f66f9e

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

2ed6a09Use autotoolized normaliz
1e91403Upgrade normaliz to official release 3.1.3

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

Description: modified (diff)
Milestone: sage-7.3sage-7.5

comment:9 Changed 6 years ago by git

Commit: 1e9140313eb2fbc1dcc35f0d47023085a8f66f9e1786d6feebef05fb460c06f38adba802ed8ae7a2

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7f85bbcUse autotoolized normaliz
a0474c0Upgrade normaliz to official release 3.1.3
1786d6fPreliminary pynormaliz package

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

Description: modified (diff)
Summary: Normaliz interfaceNormaliz/PyNormaliz interface

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

Description: modified (diff)

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

Cc: Andrey Novoseltsev added

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

Authors: Matthias Koeppe

comment:14 Changed 6 years ago by git

Commit: 1786d6feebef05fb460c06f38adba802ed8ae7a2bf94a59479dee74b0dca2284ed61fecdf6ead039

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

bf94a59Update license info

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

Description: modified (diff)

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

Cc: Winfried Bruns added

comment:17 Changed 6 years ago by git

Commit: bf94a59479dee74b0dca2284ed61fecdf6ead03984af739b3e86988e1c7b3dc39a1269b59e7702cb

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

5e87434Use autotoolized normaliz, official release 3.1.3
64e0688Preliminary pynormaliz package
84af739Add stubs for Polyhedron_normaliz

comment:18 Changed 6 years ago by git

Commit: 84af739b3e86988e1c7b3dc39a1269b59e7702cb8cfe6c07ac38084309ec055587ea1019d02f5c06

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

8cfe6c0Polyhedron_normaliz: Implement

comment:19 Changed 6 years ago by git

Commit: 8cfe6c07ac38084309ec055587ea1019d02f5c06ea9e8f625e955dd46357e50dbbca77b1eaa7f844

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

ea9e8f6MixedIntegerLinearProgram.polyhedron: Actually pass on **kwds

comment:20 Changed 6 years ago by git

Commit: ea9e8f625e955dd46357e50dbbca77b1eaa7f844f27035b185a79f4de786deab83c24d83ec49d791

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

6d31833Merge tag '7.5.beta4' into t/20885/normaliz_interface
f27035bPolyhedron_normaliz.integer_points: Implement

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

Cc: Nicolas M. Thiéry added
Summary: Normaliz/PyNormaliz interfaceNormaliz/PyNormaliz interface: Fast backend for polyhedra, integral_points

comment:22 Changed 6 years ago by git

Commit: f27035b185a79f4de786deab83c24d83ec49d791099179745f56a2ed0957ada787826fc9336cc73a

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

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

comment:23 Changed 6 years ago by Vincent Delecroix

Why did you remove the content of SPKG.txt (commit 5e87434)?

comment:24 Changed 6 years ago by Vincent Delecroix

Why don't you provide a package for pynormaliz? Downloading a non-specified version from github looks sloppy to me.

comment:25 in reply to:  23 Changed 6 years ago by Matthias Köppe

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 6 years ago by Matthias Köppe

Replying to vdelecroix:

Why don't you provide a package for pynormaliz? Downloading a non-specified version from github looks sloppy to me.

Yes, will do when it has stabilized.

comment:27 Changed 6 years ago by git

Commit: 099179745f56a2ed0957ada787826fc9336cc73a6629dc3c1bdeebca7b09ef2f8f99510449ecff56

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

6629dc3Polyhedron.integral_hull: New

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

Summary: Normaliz/PyNormaliz interface: Fast backend for polyhedra, integral_pointsNormaliz/PyNormaliz interface: Fast backend for polyhedra, integral_points, integral_hull

comment:29 Changed 6 years ago by git

Commit: 6629dc3c1bdeebca7b09ef2f8f99510449ecff5644271f86454131ec80f5b7e4ae1f43bddfee75e6

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

44271f8Polyhedron_normaliz: Handle empty polyhedra

comment:30 Changed 6 years ago by git

Commit: 44271f86454131ec80f5b7e4ae1f43bddfee75e69737e99d272b6d64cea1138d5cca1204fb7a4f67

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c23bd8dUse autotoolized normaliz, official release 3.1.3
78dd42ePreliminary pynormaliz package
6b07deeAdd stubs for Polyhedron_normaliz
d45aedfPolyhedron_normaliz: Implement
942ca7bMixedIntegerLinearProgram.polyhedron: Actually pass on **kwds
dc7289aPolyhedron_normaliz.integer_points: Implement
1a5e330Polyhedron_normaliz.integral_points(): Fast path for small bounding boxes
2975534Polyhedron.integral_hull: New
d790c15Polyhedron_normaliz: Handle empty polyhedra
9737e99Update normaliz to 3.1.4

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

Description: modified (diff)

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

Description: modified (diff)

comment:33 Changed 6 years ago by git

Commit: 9737e99d272b6d64cea1138d5cca1204fb7a4f675e6d972186762ee94b3fff60b0d78ea727128935

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

b561aabPyNormaliz: Use release 1.0
5e6d972Add "optional - pynormaliz" many times

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

Cc: Vincent Delecroix Moritz Firsching Jean-Philippe Labbé Marc Masdeu added
Status: newneeds_review

comment:35 Changed 6 years ago by Travis Scrimshaw

Branch: u/mkoeppe/normaliz_interfacepublic/geometry/normaliz_interface-20885
Commit: 5e6d972186762ee94b3fff60b0d78ea7271289356f583841aa771839f9ecbcb8186e34cad07fa014
Reviewers: Travis Scrimshaw

I was able to install everything without problems and run some examples (such as my E8 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:

6f58384Some reviewer changes and tweaks.

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

These changes are fine with me.

comment:37 Changed 6 years ago by Dima Pasechnik

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 6 years ago by Matthias Köppe

It's using the upstream distributions. No repackaging involved.

comment:39 Changed 6 years ago by Dima Pasechnik

Status: needs_reviewpositive_review

ok, good.

comment:40 Changed 6 years ago by Travis Scrimshaw

Reviewers: Travis ScrimshawTravis Scrimshaw, Dima Pasechnik

comment:41 Changed 6 years ago by Volker Braun

Branch: public/geometry/normaliz_interface-208856f583841aa771839f9ecbcb8186e34cad07fa014
Resolution: fixed
Status: positive_reviewclosed

comment:42 Changed 6 years ago by Vincent Delecroix

Commit: 6f583841aa771839f9ecbcb8186e34cad07fa014

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

I've created #22093 for this

Note: See TracTickets for help on using tickets.