Opened 3 years ago

Closed 2 years ago

#28873 closed enhancement (fixed)

Implement ambient volume of polyhedron with normaliz

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: polyhedron, normaliz, ambient volume
Cc: Jean-Philippe Labbé, Laith Rastanawi Merged in:
Authors: Jonathan Kliem Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: cc808dd (Commits, GitHub, GitLab) Commit: cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8
Dependencies: #28872 Stopgaps:

Status badges

Description (last modified by gh-kliem)

We implement the ambient volume using backend normaliz.

This is done by return 0 or infinity if the polyhedron is not full-dimensional and not compact respectively.

Otherwise, we take the induced_lattice volume and divide by factorial(self.dim()).

See section 6.1.1 of the normaliz manual on how induced_lattice volume relates to euclidean volume: https://github.com/Normaliz/Normaliz/blob/master/doc/Normaliz.pdf

This is much faster than the current method, so we set this to default if backend is normaliz.

sage: P = polytopes.dodecahedron(backend='normaliz')
sage: %time P.volume(engine='normaliz')
CPU times: user 3.91 ms, sys: 0 ns, total: 3.91 ms
Wall time: 1.49 ms
-176*sqrt5 + 400
sage: %time P.volume(engine='internal')
CPU times: user 26.5 ms, sys: 332 µs, total: 26.9 ms
Wall time: 27.5 ms
-176*sqrt5 + 400
sage: P = polytopes.one_hundred_twenty_cell(backend='normaliz')
sage: %time P.volume(engine='normaliz')
CPU times: user 1.5 s, sys: 0 ns, total: 1.5 s
Wall time: 210 ms
120*sqrt5
sage: %time P.volume(engine='internal')
CPU times: user 8.61 s, sys: 14.7 ms, total: 8.63 s
Wall time: 8.63 s
120*sqrt5
sage: P = polytopes.hypercube(6, backend='normaliz')
sage: %time P.volume(engine='normaliz')
CPU times: user 2.33 ms, sys: 0 ns, total: 2.33 ms
Wall time: 2.34 ms
64
sage: %time P.volume(engine='internal')
CPU times: user 183 ms, sys: 32 µs, total: 183 ms
Wall time: 182 ms
64

This also speeds up calculation in case the polyhedron is not full-dimensional:

sage: P = polytopes.permutahedron(6, backend='normaliz')
sage: %time P.volume(measure='induced')
CPU times: user 37.7 s, sys: 42.4 ms, total: 37.7 s
Wall time: 24.2 s
1296*sqrt(6)
sage: %time P.volume(engine='internal', measure='induced')
CPU times: user 42.9 s, sys: 71.9 ms, total: 43 s
Wall time: 41.8 s
1296*sqrt(6)

However, note that calculation of the affine hull takes quite some time in this case. So we leave the inexact normaliz option for now:

sage: %time P.volume(engine='normaliz', measure='induced')
CPU times: user 710 ms, sys: 0 ns, total: 710 ms
Wall time: 92.3 ms
3174.5387066469984

Possible follow ups:

There is probably a good and fast way to convert the lattice volume to the euclidean volume exactly. Also, once we can set up a normaliz polyhedron with both Vrep and Hrep, affine hull should be really quick.

Change History (16)

comment:1 Changed 3 years ago by gh-kliem

Branch: public/28873
Commit: 2f92b7b501c81e5dea25203681dce756307c5d6c
Status: newneeds_review

New commits:

6a15a44raised error instead of crashing for a bug in normaliz
516a622actually fixing our error
f99cf7eimplement ambient volume using normaliz
2f92b7btook care of non-compact case

comment:2 Changed 3 years ago by git

Commit: 2f92b7b501c81e5dea25203681dce756307c5d6ca35dc82c5d26c74e935f0c1b6d054e2efe3467be

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

a35dc82removed not needed method

comment:3 Changed 3 years ago by gh-kliem

Branch: public/28873public/28873-reb
Commit: a35dc82c5d26c74e935f0c1b6d054e2efe3467bea349c8ce2614c117aeea58a98d0ae0a0312035f7

New commits:

4046e3aimplement ambient volume using normaliz
485cc64took care of non-compact case
6985bf8removed not needed method
591d3b1fix pyflakes warning; added optional flag
a349c8cundid change regarding strange conversion of normaliz `Sublattice` output

comment:4 Changed 3 years ago by git

Commit: a349c8ce2614c117aeea58a98d0ae0a0312035f7add61a5dcf0194da376d34e2c3959c22d2b48bb4

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

add61a5undo false alignment

comment:5 Changed 3 years ago by gh-kliem

It should be noted, that normaliz that the conversion of the normaliz output does not work correctly when computing Sublattice for algebraic polyhedra.

Version 0, edited 3 years ago by gh-kliem (next)

comment:6 Changed 3 years ago by gh-kliem

Description: modified (diff)

comment:7 Changed 3 years ago by Erik Bray

Milestone: sage-9.0sage-9.1

Ticket retargeted after milestone closed

comment:8 Changed 3 years ago by gh-kliem

Branch: public/28873-rebpublic/28873-reb2
Commit: add61a5dcf0194da376d34e2c3959c22d2b48bb40797f5ae613226eacb57b2f1d48579f835f5ca58

Rebased.


New commits:

0797f5aimplement ambient volume using normaliz

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

Milestone: sage-9.1sage-9.2

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

comment:10 Changed 2 years ago by Jean-Philippe Labbé

Reviewers: Jean-Philippe Labbé
Status: needs_reviewneeds_work

You should add the reference to the manual in the documentation of the function. That would be a good improvement.

comment:11 Changed 2 years ago by gh-kliem

Branch: public/28873-reb2public/28873-reb3
Commit: 0797f5ae613226eacb57b2f1d48579f835f5ca586a3d5b4056a69118ef0a15ff84f3eb0ce155bf47
Status: needs_workneeds_review

New commits:

548d302Merge branch 'public/28873-reb2' of git://trac.sagemath.org/sage into public/28873-reb3
6a3d5b4added reference

comment:12 Changed 2 years ago by gh-kliem

It would be nice to have this in 9.1, if possible.

comment:13 Changed 2 years ago by Jean-Philippe Labbé

Status: needs_reviewneeds_work

Is the following "unimodual" a typo? Is unimodular meant?

+        One other possibility is to compute the scaled volume where a unimodual

There is also

+        volume of the unimodal simplex (or zero if not full-dimensional)::

Unimodular?

Could you check if this occurs in the rest of the file too?

Otherwise, the ticket looks good and the bots are green on 9.1rc0, so you can put this on positive review on my behalf once you considered the above comments.

Last edited 2 years ago by Jean-Philippe Labbé (previous) (diff)

comment:14 Changed 2 years ago by git

Commit: 6a3d5b4056a69118ef0a15ff84f3eb0ce155bf47cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8

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

cc808ddtypo with unimodular

comment:15 Changed 2 years ago by gh-kliem

Milestone: sage-9.2sage-9.1
Status: needs_workpositive_review

comment:16 Changed 2 years ago by Volker Braun

Branch: public/28873-reb3cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.