Generalize face iterator of combinatorial polyhedron to locally branched lattices

[kliem]

Currently, the face iterator requires either the lattice to be simple (all intervals not containing zero are boolean) or that it satisfies the diamond property.

With little effort, the algorithm can be exploited for intersection lattices of Coxeter arrangements.

Those lattice do no longer satisfy the diamond property, but intervals of length 2 contain at least 4 elements (locally branched).
What can happen then, is that there are multiple ways to obtain codim 2 faces from the codim 1 faces.Thus when obtaining the inclusion maximal, one needs to be careful about duplicates.

We change the algorithm to account for this. To check whether a face is inclusion maximal, we basically use strict containment check to the left and non-strict containment test to the right. Thus, not deleting the last instance of a maximal element.

Performancewise this is a mix. For small instances with few atoms in the iterator (the maximum of vertices and facets), there is a slight slowdown.
With many atoms, there will usually be an improvement, as checking a boolean is much faster than subset check of a long set.

Before:

sage: P = polytopes.Birkhoff_polytope(5)                                                                                                                                            
sage: C = CombinatorialPolyhedron(P)                                                                                                                                                
sage: %time C.f_vector()                                                                                                                                                            
CPU times: user 583 ms, sys: 385 µs, total: 583 ms
Wall time: 583 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150, 419225, 167200, 52120, 12600, 2300, 300, 25, 1)

sage: P = polytopes.permutahedron(5)                                                                                                                                                
sage: P = P.base_extend(QQ)                                                                                                                                                         
sage: Q = P.join(P.polar(in_affine_span=True))                                                                                                                                      
sage: C = CombinatorialPolyhedron(Q)                                                                                                                                                
sage: %time C.f_vector()                                                                                                                                                            
CPU times: user 111 ms, sys: 12 µs, total: 111 ms
Wall time: 111 ms
(1, 150, 3990, 25590, 69450, 95402, 69450, 25590, 3990, 150, 1)

sage: P = polytopes.permutahedron(7)                                                                                                                                                
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                       
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                               
sage: %time C.f_vector()                                                                                                                                                            
CPU times: user 270 ms, sys: 0 ns, total: 270 ms
Wall time: 270 ms
(1, 5041, 16251, 19761, 11144, 2860, 267, 1)

After:

sage: P = polytopes.Birkhoff_polytope(5)                                                                                                                                            
sage: C = CombinatorialPolyhedron(P)                                                                                                                                                
sage: %time C.f_vector()                                                                                                                                                            
CPU times: user 586 ms, sys: 0 ns, total: 586 ms
Wall time: 585 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150, 419225, 167200, 52120, 12600, 2300, 300, 25, 1)

sage: P = polytopes.permutahedron(5)                                                                                                                                                
sage: P = P.base_extend(QQ)                                                                                                                                                         
sage: Q = P.join(P.polar(in_affine_span=True))                                                                                                                                      
sage: C = CombinatorialPolyhedron(Q)                                                                                                                                                
sage: %time C.f_vector()                                                                                                                                                            
CPU times: user 143 ms, sys: 0 ns, total: 143 ms

sage: P = polytopes.permutahedron(7)                                                                                                                                                
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                       
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                               
sage: %time C.f_vector()                                                                                                                                                            
CPU times: user 178 ms, sys: 0 ns, total: 178 ms
Wall time: 178 ms
(1, 5041, 16251, 19761, 11144, 2860, 267, 1)

Note that grading is somewhat not required for the algorithm, just an upper bound on the maximal chain length. The only thing that happens is that the codimension becomes meaningless in this case.

CC: @stumpc5 @tscrim

Component: geometry

Keywords: coxeter arrangement, combinatorial polyhedron

Author: Jonathan Kliem

Branch/Commit: 5c6ccee

Reviewer: Travis Scrimshaw

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

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:2

I guess it would be too complicated to try and have both algorithms with a heuristic cutoff for determining which to use? At least the slowdown does not seem to be so bad overall except for what I might call the "intermediate" case. So I think this will be good to include. If the patchbot comes back green, then positive review.

[kliem]

comment:3

The slowness is due to the fact that checking a value in bint* takes significant amount of time in comparison to subset check, if the sets are small enough.

I guess one could check, if the sets are really small, but that would be annoying, because there would be another switch just for this tiny case.

The main point is to expose this algorithm with both flavors (locally branched and simple lattice) and use it (for now at least for simplicial complexes and flats of a matroid). Currently, this basically works and all that is missing is creating some wrapper classes.

Creating more switches, might make this harder (because this switch only works for the diamond property).

[tscrim]

comment:4

I see. Thank you for the analysis. Positive review.

[kliem]

comment:5

Thank you.

Depending on whether a use case, I might add a variant yet, that only requires atomic and coatomic, but I don't know yet (coatomic is needed so that elements can be computed by coatoms, atomic is needed so that the representation by atoms somewhat makes sense and inclusion checks can be performed).

[vbraun]

Changed branch from u/gh-kliem/generalize_algorithm_to_locally_branched to 5c6ccee