Implement the class CombinatorialPolyhedron #26887
Description
We construct a class CombinatorialPolyhedron, which collects several methods for polyhedra depending only on the combinatorial type. Actually, most of the methods will work for atomic, coatomic Eulerian lattices.
Computations can be much faster when avoiding creating explicitly the face lattice.
Example:
P = polytopes.permutahedron(6)
P.f_vector()
On my machine this takes over 8s, but it should be a matter of ms. For permutahedron(7) it takes forever and should also be a matter of ms.
Additionally, one can create the face_lattice much faster. The face_lattice of permutahedron(7) should only take few seconds. This is done by creating of lists of all faces and then quickly checking inclusions.
The crucial speed up is obtained by creating bit-vectors for the faces, each bit corresponding to a vertex. Intersection of faces is then only bitwise-and and subset check is (A & ~B == 0). Both steps only take one CPU step per 64/128/256 bits/vertices (depending on the processor). Otherwise the algorithm is pretty similar to current algorithm to create the hasse_diagram, except that it avoids double counting (and hence can calculate the f_vector) without an explicit list of all faces.
The ticket will prepare, but not use, SIMD-instructions. Enabling them will be a subject of #27103.
FOLLOW-UPS:
- implement calculation of entries in the flag-vector, this might be better, than the calculation in the face_lattice
- Improve the calculation of properties of polytopes that depend on the face-lattice (f-vector,edges, ridges, k-faces in general, edge-graph, etc.)
- Enable SIMD-instructions.
Component: geometry
Keywords: polytopes, FindPoly, f_vector, face lattice, edge graph, ridge graph
Author: Jonathan Kliem
Branch: 39a7099
Reviewer: Jeroen Demeyer, Travis Scrimshaw, Vincent Delecroix
Issue created by migration from https://trac.sagemath.org/ticket/26887