id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
28873 Implement ambient volume of polyhedron with normaliz 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." enhancement closed major sage-9.1 geometry fixed polyhedron, normaliz, ambient volume Jean-Philippe Labbé Laith Rastanawi Jonathan Kliem Jean-Philippe Labbé N/A cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8 cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8 #28872