Implement ambient volume of polyhedron with normaliz

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

Depends on #28872

CC: @jplab @LaisRast

Component: geometry

Keywords: polyhedron, normaliz, ambient volume

Author: Jonathan Kliem

Branch/Commit: cc808dd

Reviewer: Jean-Philippe Labbé

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

[kliem]

New commits:

6a15a44	raised error instead of crashing for a bug in normaliz
516a622	actually fixing our error
f99cf7e	implement ambient volume using normaliz
2f92b7b	took care of non-compact case

[kliem]

Commit: 2f92b7b

[kliem]

Branch: public/28873

[sagetrac-git]

Changed commit from 2f92b7b to a35dc82

[sagetrac-git]

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

a35dc82

removed not needed method

[kliem]

Changed branch from public/28873 to public/28873-reb

[kliem]

Changed commit from a35dc82 to a349c8c

[kliem]

New commits:

4046e3a	implement ambient volume using normaliz
485cc64	took care of non-compact case
6985bf8	removed not needed method
591d3b1	fix pyflakes warning; added optional flag
a349c8c	undid change regarding strange conversion of normaliz `Sublattice` output

[sagetrac-git]

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

add61a5

undo false alignment

[sagetrac-git]

Changed commit from a349c8c to add61a5

[kliem]

comment:5

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

[embray]

comment:7

Ticket retargeted after milestone closed

[kliem]

comment:8

Rebased.

---

New commits:

0797f5a

implement ambient volume using normaliz

[kliem]

Changed branch from public/28873-reb to public/28873-reb2

[kliem]

Changed commit from add61a5 to 0797f5a

[mkoeppe]

comment:9

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.

[jplab]

Reviewer: Jean-Philippe Labbé

[jplab]

comment:10

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

[kliem]

Changed commit from 0797f5a to 6a3d5b4

[kliem]

Changed branch from public/28873-reb2 to public/28873-reb3

[kliem]

New commits:

548d302	Merge branch 'public/28873-reb2' of git://trac.sagemath.org/sage into public/28873-reb3
6a3d5b4	added reference

[kliem]

comment:12

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

[jplab]

comment:13

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.

[sagetrac-git]

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

cc808dd

typo with unimodular

[sagetrac-git]

Changed commit from 6a3d5b4 to cc808dd

[vbraun]

Changed branch from public/28873-reb3 to cc808dd