Opened 4 years ago

Closed 3 years ago

#22310 closed enhancement (fixed)

Use PPL for facet normals of full-dimensional polytopes

Reported by: novoselt Owned by:
Priority: major Milestone: sage-7.6
Component: geometry Keywords: days85
Cc: vbraun, tscrim Merged in:
Authors: Andrey Novoseltsev Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: d244793 (Commits) Commit: d24479380a46e868d64c9fe8a228813259ad9414
Dependencies: #22309 Stopgaps:

Description (last modified by 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

Change History (10)

comment:1 Changed 4 years ago by novoselt

  • Branch set to u/novoselt/PPL_for_fulldim_normals

comment:2 Changed 4 years ago by novoselt

  • Cc vbraun added
  • Commit set to d24479380a46e868d64c9fe8a228813259ad9414
  • Status changed from new to needs_review

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:

a262ec3Make dual nef-partitions conveniently ordered
6b5972cFix nef-partition ordering in doctests
2e26768Add NefCompleteIntersection.cohomology_class
7afca73Add Cayley polytopes/cones to dosctring of NefPartition
e78ff49Add PPL representation to LatticePolytope
5c286e4Use PPL for computing vertices of LatticePolytope
db3b54eFix doctests - mostly due to different order of vertices
5281cf4Use PPL for facet normals of full-dimensional polytopes
d244793Update a lot of toric doctests for the new facet order

comment:3 Changed 3 years ago by novoselt

  • Description modified (diff)

comment:4 Changed 3 years ago by novoselt

  • Cc tscrim added

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.

comment:5 Changed 3 years ago by tscrim

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

comment:6 Changed 3 years ago by tscrim

  • Keywords days85 added
  • Reviewers set to Travis Scrimshaw

comment:7 Changed 3 years ago by novoselt

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 ;-)

comment:8 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

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.

comment:9 Changed 3 years ago by novoselt

Thanks a lot! Naturally, feel free to move to the next one, but it gets more involved, although I tried to make each commit sensible on its own...

comment:10 Changed 3 years ago by vbraun

  • Branch changed from u/novoselt/PPL_for_fulldim_normals to d24479380a46e868d64c9fe8a228813259ad9414
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.