#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: jipilab, gh-LaisRast 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 17 months ago by gh-kliem

  • Branch set to public/28873
  • Commit set to 2f92b7b501c81e5dea25203681dce756307c5d6c
  • Status changed from new to needs_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 17 months ago by git

  • Commit changed from 2f92b7b501c81e5dea25203681dce756307c5d6c to a35dc82c5d26c74e935f0c1b6d054e2efe3467be

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

a35dc82removed not needed method

comment:3 Changed 16 months ago by gh-kliem

  • Branch changed from public/28873 to public/28873-reb
  • Commit changed from a35dc82c5d26c74e935f0c1b6d054e2efe3467be to a349c8ce2614c117aeea58a98d0ae0a0312035f7

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 16 months ago by git

  • Commit changed from a349c8ce2614c117aeea58a98d0ae0a0312035f7 to add61a5dcf0194da376d34e2c3959c22d2b48bb4

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

add61a5undo false alignment

comment:5 Changed 16 months ago by gh-kliem

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

Last edited 16 months ago by gh-kliem (previous) (diff)

comment:6 Changed 16 months ago by gh-kliem

  • Description modified (diff)

comment:7 Changed 16 months ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:8 Changed 13 months ago by gh-kliem

  • Branch changed from public/28873-reb to public/28873-reb2
  • Commit changed from add61a5dcf0194da376d34e2c3959c22d2b48bb4 to 0797f5ae613226eacb57b2f1d48579f835f5ca58

Rebased.


New commits:

0797f5aimplement ambient volume using normaliz

comment:9 Changed 12 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-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 12 months ago by jipilab

  • Reviewers set to Jean-Philippe Labbé
  • Status changed from needs_review to needs_work

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

comment:11 Changed 12 months ago by gh-kliem

  • Branch changed from public/28873-reb2 to public/28873-reb3
  • Commit changed from 0797f5ae613226eacb57b2f1d48579f835f5ca58 to 6a3d5b4056a69118ef0a15ff84f3eb0ce155bf47
  • Status changed from needs_work to needs_review

New commits:

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

comment:12 Changed 12 months ago by gh-kliem

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

comment:13 Changed 12 months ago by jipilab

  • Status changed from needs_review to needs_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 12 months ago by jipilab (previous) (diff)

comment:14 Changed 12 months ago by git

  • Commit changed from 6a3d5b4056a69118ef0a15ff84f3eb0ce155bf47 to cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8

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

cc808ddtypo with unimodular

comment:15 Changed 12 months ago by gh-kliem

  • Milestone changed from sage-9.2 to sage-9.1
  • Status changed from needs_work to positive_review

comment:16 Changed 12 months ago by vbraun

  • Branch changed from public/28873-reb3 to cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.