Opened 3 years ago
Closed 3 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:  JeanPhilippe Labbé, Laith Rastanawi  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:  → public/28873 

Commit:  → 2f92b7b501c81e5dea25203681dce756307c5d6c 
Status:  new → needs_review 
comment:2 Changed 3 years ago by
Commit:  2f92b7b501c81e5dea25203681dce756307c5d6c → 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:  public/28873 → public/28873reb 

Commit:  a35dc82c5d26c74e935f0c1b6d054e2efe3467be → a349c8ce2614c117aeea58a98d0ae0a0312035f7 
comment:4 Changed 3 years ago by
Commit:  a349c8ce2614c117aeea58a98d0ae0a0312035f7 → 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:  sage9.0 → sage9.1 

Ticket retargeted after milestone closed
comment:8 Changed 3 years ago by
Branch:  public/28873reb → public/28873reb2 

Commit:  add61a5dcf0194da376d34e2c3959c22d2b48bb4 → 0797f5ae613226eacb57b2f1d48579f835f5ca58 
comment:9 Changed 3 years ago by
Milestone:  sage9.1 → 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 3 years ago by
Reviewers:  → JeanPhilippe Labbé 

Status:  needs_review → 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 3 years ago by
Branch:  public/28873reb2 → public/28873reb3 

Commit:  0797f5ae613226eacb57b2f1d48579f835f5ca58 → 6a3d5b4056a69118ef0a15ff84f3eb0ce155bf47 
Status:  needs_work → needs_review 
comment:13 Changed 3 years ago by
Status:  needs_review → 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 3 years ago by
Commit:  6a3d5b4056a69118ef0a15ff84f3eb0ce155bf47 → cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8 

Branch pushed to git repo; I updated commit sha1. New commits:
cc808dd  typo with unimodular

comment:15 Changed 3 years ago by
Milestone:  sage9.2 → sage9.1 

Status:  needs_work → positive_review 
comment:16 Changed 3 years ago by
Branch:  public/28873reb3 → cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8 

Resolution:  → fixed 
Status:  positive_review → 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