Opened 3 years ago

Closed 3 years ago

# Implement ambient volume of polyhedron with normaliz

Reported by: Owned by: gh-kliem major sage-9.1 geometry polyhedron, normaliz, ambient volume Jean-Philippe Labbé, Laith Rastanawi 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: → public/28873 → 2f92b7b501c81e5dea25203681dce756307c5d6c new → 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: 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 gh-kliem

Branch: public/28873 → public/28873-reb a35dc82c5d26c74e935f0c1b6d054e2efe3467be → 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

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 Erik Bray

Milestone: sage-9.0 → sage-9.1

Ticket retargeted after milestone closed

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

Branch: public/28873-reb → public/28873-reb2 add61a5dcf0194da376d34e2c3959c22d2b48bb4 → 0797f5ae613226eacb57b2f1d48579f835f5ca58

Rebased.

New commits:

 ​0797f5a `implement ambient volume using normaliz`

### comment:9 Changed 3 years ago by Matthias Köppe

Milestone: sage-9.1 → 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 3 years ago by Jean-Philippe Labbé

Reviewers: → Jean-Philippe Labbé 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 gh-kliem

Branch: public/28873-reb2 → public/28873-reb3 0797f5ae613226eacb57b2f1d48579f835f5ca58 → 6a3d5b4056a69118ef0a15ff84f3eb0ce155bf47 needs_work → 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 3 years ago by gh-kliem

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

### comment:13 Changed 3 years ago by Jean-Philippe Labbé

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 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 3 years ago by Jean-Philippe Labbé (previous) (diff)

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

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

Milestone: sage-9.2 → sage-9.1 needs_work → positive_review

### comment:16 Changed 3 years ago by Volker Braun

Branch: public/28873-reb3 → cc808ddf0aa4c094426d799f26bebaf5a2b5c3e8 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.