Opened 3 years ago

Closed 2 years ago

# Implement ambient volume of polyhedron with normaliz

Reported by: Owned by: gh-kliem major sage-9.1 geometry polyhedron, normaliz, ambient volume jipilab, gh-LaisRast Jonathan Kliem Jean-Philippe Labbé N/A cc808dd cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8 #28872

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
```

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.

### comment:1 Changed 3 years ago by gh-kliem

• Branch set to public/28873
• Commit set to 2f92b7b501c81e5dea25203681dce756307c5d6c
• Status changed from new to needs_review

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`

### comment:2 Changed 3 years ago by git

• 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 gh-kliem

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

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`

### comment:4 Changed 3 years ago by git

• 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 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 3 years ago by gh-kliem (previous) (diff)

### comment:6 Changed 3 years ago by gh-kliem

• Description modified (diff)

### comment:7 Changed 3 years ago by embray

• Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

### comment:8 Changed 2 years ago by gh-kliem

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

Rebased.

New commits:

 ​0797f5a `implement ambient volume using normaliz`

### comment:9 Changed 2 years 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 2 years 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 2 years 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:

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

### comment:12 Changed 2 years ago by gh-kliem

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

### comment:13 Changed 2 years 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 2 years ago by jipilab (previous) (diff)

### comment:14 Changed 2 years ago by git

• 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 gh-kliem

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

### comment:16 Changed 2 years 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.