Lattice Polytopes: Obtain facets directly from facet_normals

[kliem]

Currently, the facets of lattice polytopes are obtained from the face lattice. This is somewhat slow, but most importantly this is a problem for CombinatorialPolyhedron, which uses the method facets to obtain the combinatorial structure. So CombinatorialPolyhedron cannot be be used for computing the face lattice of lattice polytopes.

Solution: We won't fix this. Instead #28960 initializes CombinatorialPolyhedron from (a new method) incidence_matrix. This implicitely uses facet_normals instead of facets. This why CombinatorialPolyhedron is independent of the face lattice computation.

CC: @jplab @LaisRast

Component: geometry

Keywords: lattice polytopes, facets

Author: Jonathan Kliem

Reviewer: Andrey Novoseltsev

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

[kliem]

Commit: 5d9eff3

[kliem]

New commits:

5d9eff3

directly obtain facets of lattice polytope

[kliem]

Branch: public/28735

[novoselt]

comment:2

While it certainly makes sense, some things should be addressed:

1. Caching of facets - while the existing code computes more than necessary, it does it once and on the second invocation nothing is computed at all, plus all the properties of the facets (like lattice point count) are cached as well.
2. Face lattice methods - is it still possible with this change to ask for neighbours of a facet or its own facets and get the same results as before? I have doubts about it as it relied on facets being elements of a poset.
3. Sorting in low-dimensional cases - there is care the in the existing code to have consistent order of vertices and 0-dimensional faces, as well as facet normals and facets. And sometimes these coinside. Will the new code preserve the order?

As a possible easy solution - facets may take some argument like from_lattice=True which will trigger full lattice computation when True (default) and when False it will check if lattice is already computed (in which case there is no harm in using it) and if not - use the suggested code.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a06009f	cache facets, facets are identical in face lattice
76e9daf	return facets by ambient faces, if self is an ambient face of another polyhedron

[sagetrac-git]

Changed commit from 5d9eff3 to 76e9daf

[kliem]

comment:4

Thanks for the comments.

Replying to @novoselt:

While it certainly makes sense, some things should be addressed:

1. Caching of facets - while the existing code computes more than necessary, it does it once and on the second invocation nothing is computed at all, plus all the properties of the facets (like lattice point count) are cached as well.

Sure.

2. Face lattice methods - is it still possible with this change to ask for neighbours of a facet or its own facets and get the same results as before? I have doubts about it as it relied on facets being elements of a poset.

It seems to still work:

sage: o = lattice_polytope.cross_polytope(5)
sage: f = o.facets()[0]
sage: f.facet_of()
(5-d reflexive polytope in 5-d lattice M,)
sage: L = o.face_lattice()
sage: D = L.hasse_diagram()
sage: D.neighbors(f)
[3-d face of 5-d reflexive polytope in 5-d lattice M,
 5-d reflexive polytope in 5-d lattice M,
 3-d face of 5-d reflexive polytope in 5-d lattice M,
 3-d face of 5-d reflexive polytope in 5-d lattice M,
 3-d face of 5-d reflexive polytope in 5-d lattice M,
 3-d face of 5-d reflexive polytope in 5-d lattice M]
sage: f.facet_of()
(5-d reflexive polytope in 5-d lattice M,)
sage: 

Nevertheless, I adopted face_lattice to return exactly the facets in codimension 1.

I also changed my could to only be applied, when self is self.ambient().

3. Sorting in low-dimensional cases - there is care the in the existing code to have consistent order of vertices and 0-dimensional faces, as well as facet normals and facets. And sometimes these coinside. Will the new code preserve the order?

My facets should be in exactly the same order, as they used to be, as I just took the code from face_lattice. They are also in the same order as the normals. So anything else would be very strange. Wouldn't it?

As a possible easy solution - facets may take some argument like from_lattice=True which will trigger full lattice computation when True (default) and when False it will check if lattice is already computed (in which case there is no harm in using it) and if not - use the suggested code.

Eventually, it makes sense to cache the hasse diagram instead of the FiniteLatticePoset. See https://groups.google.com/d/msg/sage-devel/UuSDdN9QC3M/i2Uzp2SzEAAJ.

---

New commits:

a06009f	cache facets, facets are identical in face lattice
76e9daf	return facets by ambient faces, if self is an ambient face of another polyhedron

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d1e022b

simplified construction

[sagetrac-git]

Changed commit from 76e9daf to d1e022b

[kliem]

comment:7

Actually, I think I'm going to change the design a bit.

• Make LPFace a method of the lattice polytope (cached), which
  • if self.ambient() is self works as it is
  • otherwise transform the indices to ambient indices (using cached dictionaries) and then call LPFace of ambient

This way one can obtain facets directly from any lattice polytope. This will also allow to obtain faces directly from an interator instead of from the face lattice.

[novoselt]

comment:8

By face lattice methods I actually meant methods of facets which are related to the lattice:

sage: sage: o = lattice_polytope.cross_polytope(5)
....: sage: f = o.facets()[0]
....: sage: f.facet_of()
....: 
(5-d reflexive polytope in 5-d lattice M,)
sage: f.adjacent()
(4-d face of 5-d reflexive polytope in 5-d lattice M,
 4-d face of 5-d reflexive polytope in 5-d lattice M,
 4-d face of 5-d reflexive polytope in 5-d lattice M,
 4-d face of 5-d reflexive polytope in 5-d lattice M,
 4-d face of 5-d reflexive polytope in 5-d lattice M)

Will this adjacent method work with your design? What would be nice (and perhaps your last comment was about it as well) is to have an ability to construct standalone faces, but whenever they are requested again for whatever reason (e.g. because the full face lattice is computed) - exactly the same objects are returned.

[novoselt]

comment:9

Also a general remark on these improvements and optimizations - they are very welcome, especially since I have no time anymore to work on them myself! But please keep in mind the use case these classes were introduced - working with a lot of quite small polytopes (reflexive, their faces and subpolytopes) where faces and numbers of lattice points are requested repeatedly. So whatever optimizations are added to initial constructions should not affect caching of stuff for later reuse. Thank you!

[kliem]

comment:10

Ok, I keep that in mind.

A few sentences about my motivation:

I mainly just wanted to compute the face lattice by CombinatorialPolyhedron. However, it doesn't make any sense to initialize it from the facets, which are in turn taken from the face lattice.

One intermediate step, is to create the incidence matrix (#28743). This is implicitly done for the face lattice anyway. (Actually one can obtain the combinatorial polyhedron instead from the incidence matrix.)

Maybe I just replace face lattice (in the self is self.ambient() case) and leave everything else the way it is.

To avoid memory leak, it makes also sense to cache the hasse diagram/digraph instead of FiniteLatticePoset (I was told that this is cached anyway). As it looks, many methods can then just call the hasse diagram directly.

[embray]

comment:11

Ticket retargeted after milestone closed

[kliem]

Changed commit from d1e022b to none

[kliem]

Changed branch from public/28735 to none

[novoselt]

Reviewer: Andrey Novoseltsev

[kliem]

comment:14

While this ticket is not closed, I updated the description to help people understand what was going on and why we this ticket is a "won't fix".