Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#20885 closed enhancement (fixed)

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

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.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:

Status badges

Description (last modified by mkoeppe)

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

  • Cc tscrim added
  • Description modified (diff)

comment:2 Changed 5 years ago by mkoeppe

  • Cc dimpase added
  • Description modified (diff)
  • Type changed from task to enhancement

comment:3 Changed 5 years ago by mkoeppe

  • Description modified (diff)

comment:4 Changed 5 years ago by mkoeppe

  • Branch set to u/mkoeppe/normaliz_interface

comment:5 Changed 5 years ago by mkoeppe

  • Commit set to 8881612b46c5948cd305fd8e3ad56fb487478991
  • Description modified (diff)

New commits:

8881612Use autotoolized normaliz

comment:6 Changed 5 years ago by mkoeppe

  • Cc yzh added

comment:7 Changed 5 years ago by git

  • Commit changed from 8881612b46c5948cd305fd8e3ad56fb487478991 to 1e9140313eb2fbc1dcc35f0d47023085a8f66f9e

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

  • Description modified (diff)
  • Milestone changed from sage-7.3 to sage-7.5

comment:9 Changed 5 years ago by git

  • Commit changed from 1e9140313eb2fbc1dcc35f0d47023085a8f66f9e to 1786d6feebef05fb460c06f38adba802ed8ae7a2

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

  • Description modified (diff)
  • Summary changed from Normaliz interface to Normaliz/PyNormaliz interface

comment:11 Changed 5 years ago by mkoeppe

  • Description modified (diff)

comment:12 Changed 5 years ago by mkoeppe

  • Cc novoselt added

comment:13 Changed 5 years ago by mkoeppe

  • Authors set to Matthias Koeppe

comment:14 Changed 5 years ago by git

  • Commit changed from 1786d6feebef05fb460c06f38adba802ed8ae7a2 to bf94a59479dee74b0dca2284ed61fecdf6ead039

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

bf94a59Update license info

comment:15 Changed 5 years ago by mkoeppe

  • Description modified (diff)

comment:16 Changed 5 years ago by mkoeppe

  • Cc Winfried added

comment:17 Changed 5 years ago by git

  • Commit changed from bf94a59479dee74b0dca2284ed61fecdf6ead039 to 84af739b3e86988e1c7b3dc39a1269b59e7702cb

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

  • Commit changed from 84af739b3e86988e1c7b3dc39a1269b59e7702cb to 8cfe6c07ac38084309ec055587ea1019d02f5c06

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

8cfe6c0Polyhedron_normaliz: Implement

comment:19 Changed 5 years ago by git

  • Commit changed from 8cfe6c07ac38084309ec055587ea1019d02f5c06 to ea9e8f625e955dd46357e50dbbca77b1eaa7f844

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

ea9e8f6MixedIntegerLinearProgram.polyhedron: Actually pass on **kwds

comment:20 Changed 5 years ago by git

  • Commit changed from ea9e8f625e955dd46357e50dbbca77b1eaa7f844 to f27035b185a79f4de786deab83c24d83ec49d791

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

  • 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 git

  • Commit changed from f27035b185a79f4de786deab83c24d83ec49d791 to 099179745f56a2ed0957ada787826fc9336cc73a

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

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

comment:23 follow-up: Changed 5 years ago by vdelecroix

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

comment:24 follow-up: Changed 5 years ago by vdelecroix

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

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 mkoeppe

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

  • Commit changed from 099179745f56a2ed0957ada787826fc9336cc73a to 6629dc3c1bdeebca7b09ef2f8f99510449ecff56

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

6629dc3Polyhedron.integral_hull: New

comment:28 Changed 5 years ago by mkoeppe

  • 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 git

  • Commit changed from 6629dc3c1bdeebca7b09ef2f8f99510449ecff56 to 44271f86454131ec80f5b7e4ae1f43bddfee75e6

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

44271f8Polyhedron_normaliz: Handle empty polyhedra

comment:30 Changed 5 years ago by git

  • Commit changed from 44271f86454131ec80f5b7e4ae1f43bddfee75e6 to 9737e99d272b6d64cea1138d5cca1204fb7a4f67

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

  • Description modified (diff)

comment:32 Changed 5 years ago by mkoeppe

  • Description modified (diff)

comment:33 Changed 5 years ago by git

  • Commit changed from 9737e99d272b6d64cea1138d5cca1204fb7a4f67 to 5e6d972186762ee94b3fff60b0d78ea727128935

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

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

comment:34 Changed 5 years ago by mkoeppe

  • Cc vdelecroix moritz jipilab mmasdeu added
  • Status changed from new to needs_review

comment:35 Changed 5 years ago by tscrim

  • Branch changed from u/mkoeppe/normaliz_interface to public/geometry/normaliz_interface-20885
  • 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 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 5 years ago by mkoeppe

These changes are fine with me.

comment:37 Changed 5 years ago by dimpase

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 mkoeppe

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

comment:39 Changed 5 years ago by dimpase

  • Status changed from needs_review to positive_review

ok, good.

comment:40 Changed 5 years ago by tscrim

  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Dima Pasechnik

comment:41 Changed 5 years ago by vbraun

  • Branch changed from public/geometry/normaliz_interface-20885 to 6f583841aa771839f9ecbcb8186e34cad07fa014
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:42 Changed 5 years ago by vdelecroix

  • Commit 6f583841aa771839f9ecbcb8186e34cad07fa014 deleted

comment:43 Changed 5 years ago by mkoeppe

I've created #22093 for this

Note: See TracTickets for help on using tickets.