Use PPL for facet normals of full-dimensional polytopes

[novoselt]

Before:

sage: timeit("LatticePolytope(lattice_polytope.cross_polytope(3).vertices()).facet_normals()")
5 loops, best of 3: 43.2 ms per loop

After:

sage: timeit("LatticePolytope(lattice_polytope.cross_polytope(3).vertices()).facet_normals()")
125 loops, best of 3: 6.81 ms per loop

PPL will of course work for non-full-dimensional polytopes as well, however the treatment of this case is spread around several places and its removal will be treated separately. Once this is done the speed up will be even more significant.

Next in the chain of lattice polytope improvements is #22391

Depends on #22309

CC: @vbraun @tscrim

Component: geometry

Keywords: days85

Author: Andrey Novoseltsev

Branch/Commit: d244793

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/22310

[novoselt]

Branch: u/novoselt/PPL_for_fulldim_normals

[novoselt]

comment:2

Hey Volker! Looking forward to non-full-dimensional case: many years ago #9188 promised in documentation that

        If this polytope is not full-dimensional, facet normals will be
        orthogonal to the integer kernel of the affine subspace spanned by
        this polytope.

I can't recall any reason why this orthogonality would be of any importance, can you? Trying to ensure it (unless PPL for some reason guarantees it already) involves a somewhat long chain of matrix manipulations that you eventually got correct and while it is sad to remove it, doing so will definitely simplify the code and likely make it noticeably faster.

---

New commits:

a262ec3	Make dual nef-partitions conveniently ordered
6b5972c	Fix nef-partition ordering in doctests
2e26768	Add NefCompleteIntersection.cohomology_class
7afca73	Add Cayley polytopes/cones to dosctring of NefPartition
e78ff49	Add PPL representation to LatticePolytope
5c286e4	Use PPL for computing vertices of LatticePolytope
db3b54e	Fix doctests - mostly due to different order of vertices
5281cf4	Use PPL for facet normals of full-dimensional polytopes
d244793	Update a lot of toric doctests for the new facet order

[novoselt]

Commit: d244793

[novoselt]

Description changed:

--- 
+++ 
@@ -11,3 +11,5 @@
 125 loops, best of 3: 6.81 ms per loop
 ```
 PPL will of course work for non-full-dimensional polytopes as well, however the treatment of this case is spread around several places and its removal will be treated separately. Once this is done the speed up will be even more significant.
+
+Next in the chain of lattice polytope improvements is #22391

[novoselt]

comment:4

Hi, Travis! Since you were so kind to review the dependency, do you care to take a look at this one? The real change is in the first short commit (the second one is doctest fixing) and that one is mostly copy-pasting old code and constructing the same thing from PPL functions rather than PALP format.

[tscrim]

comment:5

Are the changes in schemes/toric all coming from different orderings of (some of) the outputs, or are they honest changes?

[tscrim]

Changed keywords from none to days85

[tscrim]

Reviewer: Travis Scrimshaw

[novoselt]

comment:7

Um, what are "honest changes"? The cause for all of them is the change in ordering. Since toric computations often rely on both vertices and normals, things got affected quite a bit. Some tests had to be adjusted themselves (i.e. not just output) because they relied on indices of normals in the list, e.g. for charts.

I've done my best to go through all affected cases carefully and reading the context to make sure that they still made sense, although I don't know of an easy way to verify my claim ;-)

[tscrim]

comment:8

I would consider than an honest change, but if you say they are equivalent answers, then that is good enough for me. Thanks; positive review.