Opened 3 years ago
Closed 2 years ago
#28873 closed enhancement (fixed)
Implement ambient volume of polyhedron with normaliz
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  geometry  Keywords:  polyhedron, normaliz, ambient volume 
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  cc808dd (Commits, GitHub, GitLab)  Commit:  cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8 
Dependencies:  #28872  Stopgaps: 
Description (last modified by )
We implement the ambient volume using backend normaliz.
This is done by return 0 or infinity if the polyhedron is not fulldimensional 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 fulldimensional:
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
 Branch set to public/28873
 Commit set to 2f92b7b501c81e5dea25203681dce756307c5d6c
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
 Commit changed from 2f92b7b501c81e5dea25203681dce756307c5d6c to a35dc82c5d26c74e935f0c1b6d054e2efe3467be
Branch pushed to git repo; I updated commit sha1. New commits:
a35dc82  removed not needed method

comment:3 Changed 3 years ago by
 Branch changed from public/28873 to public/28873reb
 Commit changed from a35dc82c5d26c74e935f0c1b6d054e2efe3467be to a349c8ce2614c117aeea58a98d0ae0a0312035f7
comment:4 Changed 3 years ago by
 Commit changed from a349c8ce2614c117aeea58a98d0ae0a0312035f7 to add61a5dcf0194da376d34e2c3959c22d2b48bb4
Branch pushed to git repo; I updated commit sha1. New commits:
add61a5  undo false alignment

comment:5 Changed 3 years ago by
It should be noted that the conversion of the normaliz output does not work correctly when computing Sublattice
for algebraic polyhedra.
comment:6 Changed 3 years ago by
 Description modified (diff)
comment:7 Changed 3 years ago by
 Milestone changed from sage9.0 to sage9.1
Ticket retargeted after milestone closed
comment:8 Changed 2 years ago by
 Branch changed from public/28873reb to public/28873reb2
 Commit changed from add61a5dcf0194da376d34e2c3959c22d2b48bb4 to 0797f5ae613226eacb57b2f1d48579f835f5ca58
comment:9 Changed 2 years ago by
 Milestone changed from sage9.1 to sage9.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
 Reviewers set to JeanPhilippe 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 2 years ago by
 Branch changed from public/28873reb2 to public/28873reb3
 Commit changed from 0797f5ae613226eacb57b2f1d48579f835f5ca58 to 6a3d5b4056a69118ef0a15ff84f3eb0ce155bf47
 Status changed from needs_work to needs_review
comment:12 Changed 2 years ago by
It would be nice to have this in 9.1, if possible.
comment:13 Changed 2 years ago by
 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 fulldimensional)::
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.
comment:14 Changed 2 years ago by
 Commit changed from 6a3d5b4056a69118ef0a15ff84f3eb0ce155bf47 to cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8
Branch pushed to git repo; I updated commit sha1. New commits:
cc808dd  typo with unimodular

comment:15 Changed 2 years ago by
 Milestone changed from sage9.2 to sage9.1
 Status changed from needs_work to positive_review
comment:16 Changed 2 years ago by
 Branch changed from public/28873reb3 to cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
raised error instead of crashing for a bug in normaliz
actually fixing our error
implement ambient volume using normaliz
took care of noncompact case