Implement the class CombinatorialPolyhedron

[kliem]

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.

CC: @stumpc5 @jplab @tscrim

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

[kliem]

Branch: u/gh-kliem/improve_f_vector_etc__for_polytopes

[fchapoton]

Commit: d0dba61

[fchapoton]

comment:2

the branch is almost empty (no meaningful changes)

---

New commits:

d0dba61

first push test

[sagetrac-git]

Changed commit from d0dba61 to 3f1600e

[sagetrac-git]

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

a596e0c	Created a class CombinatorialType which is a wrapper for a cpp class
3f1600e	added the files

[kliem]

Author: Jonathan Kliem

[kliem]

Changed keywords from polytopes, FindPoly to polytopes, FindPoly, f_vector, face_lattic

[sagetrac-git]

Changed commit from 3f1600e to 03fe21f

[sagetrac-git]

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

3b10c24	moved the files to the polyhedron folder
03fe21f	added the new files

[sagetrac-git]

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

99eda99	Before Renaming CombinatorialType to CombinatorialPolytope
7efe6a2	After Renaming CombinatorialType to CombinatorialPolytope
24949d9	This should be mostly done now. Some minor changes are missing, also documentation needs to be done'

[sagetrac-git]

Changed commit from 03fe21f to 24949d9

[sagetrac-git]

Changed commit from 24949d9 to 8c5d21a

[sagetrac-git]

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

8c5d21a

some minor changes

[sagetrac-git]

Changed commit from 8c5d21a to a63c68f

[sagetrac-git]

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

a63c68f

Preparing a function to get all k-faces

[sagetrac-git]

Changed commit from a63c68f to 580980b

[sagetrac-git]

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

580980b

some work on generating all k-faces of the polyhedron

[sagetrac-git]

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

591ed26

hasse_diagram is mostly working now, it is much faster than the old hasse_diagram of polyhedron

[sagetrac-git]

Changed commit from 580980b to 591ed26

[kliem]

Changed keywords from polytopes, FindPoly, f_vector, face_lattic to polytopes, FindPoly, f_vector, face lattice, flag vector, edge graph, ridge grapg

[sagetrac-git]

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

576905d

flag vectors seem to work now

[videlec]

comment:229

Please move any further discussion to new tickets.

[fchapoton]

Changed dependencies from #27292 to none

[vbraun]

comment:231

Fails on e.g. Debian 8:

[sagelib-8.8] [ 98/495] gcc -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -fPIC -I/home/buildbot/slave/sage_git/build/local/include/python2.7 -c sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc -o build/temp.linux-i686-2.7/sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.o
[sagelib-8.8] In file included from /usr/include/c++/4.9/cstdint:35:0,
[sagelib-8.8]                  from sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:13:
[sagelib-8.8] /usr/include/c++/4.9/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
[sagelib-8.8]  #error This file requires compiler and library support for the \
[sagelib-8.8]   ^
[sagelib-8.8] sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:27:22: error: ‘is_subset’ declared as an ‘inline’ variable

[kliem]

comment:232

As far as I know there are two ways of solving this.

Either use the macro __cplusplus to determine the c++ version and not use inline if it is not available. (This would be a quick fix I guess).

Use -std=c++11 as compile argument.

Any opinions?

Replying to @vbraun:

Fails on e.g. Debian 8:

[sagelib-8.8] [ 98/495] gcc -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -fPIC -I/home/buildbot/slave/sage_git/build/local/include/python2.7 -c sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc -o build/temp.linux-i686-2.7/sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.o
[sagelib-8.8] In file included from /usr/include/c++/4.9/cstdint:35:0,
[sagelib-8.8]                  from sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:13:
[sagelib-8.8] /usr/include/c++/4.9/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
[sagelib-8.8]  #error This file requires compiler and library support for the \
[sagelib-8.8]   ^
[sagelib-8.8] sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:27:22: error: ‘is_subset’ declared as an ‘inline’ variable

[videlec]

comment:233

Replying to @kliem:

As far as I know there are two ways of solving this.

Either use the macro __cplusplus to determine the c++ version and not use inline if it is not available. (This would be a quick fix I guess).

Use -std=c++11 as compile argument.

Any opinions?

Add the -std=c++11 option to the concerned extension

    Extension('sage.geometry.polyhedron.combinatorial_polyhedron.bit_vector_operations.cc',
              sources = ['sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc'],
              extra_compile_args=['-std=c++11']),

[sagetrac-git]

Changed commit from 8765313 to 39a7099

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

092c916	split list_of_faces, fixed imports etc.
46d54b3	added documentation and examples to each module
8ee84ce	correct hyperlinks
3869c1f	documentation fix
938b04c	Do not iterate twice for CombinatorialPolyhedron.facets()
e6d5b08	added combinatorial face
69e28ba	improved docstring in list_of_all_faces
1e2a52b	fixed small issues
e298ed0	A number of small edits.
39a7099	added compile argument -std=c++11

[kliem]

comment:235

added compile argument, this should work now (also #27987 fixes already a bug in the unbounded case)

Thanks for all the help, btw.

[vbraun]

Changed branch from public/26887 to 39a7099

[fchapoton]

Changed commit from 39a7099 to none

[fchapoton]

comment:239

This triggers a new failing doctest with python3-sage:

sage -t --long src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx
**********************************************************************
File "src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 937, in sage.geometry.polyhedron.combinatorial_polyhedron.base.CombinatorialPolyhedron.edge_graph
Failed example:
    G.degree()
Expected:
    [4, 3, 4, 3, 4]
Got:
    [3, 4, 4, 3, 4]

[fchapoton]

comment:240

I have made #28153 for the py3 problem, please review.

[kliem]

comment:241

Some attributes like bitrep_vertices might have been an unfortunate choice:

As they are accessed by other classes, I'm forced to compute e.g. bitrep_vertices on initialization. If CombinatorialPolyhedron was ever to be a parent of Polyhedron_base (see #10777), this would force a polyhedron to compute the incidence matrix right away.

From my understanding, the decorator @lazy_attribute is not available for extension types directly. I'm thinking of changing those attributes to methods, such that there is a method bitrep_facets and an attribute _bitrep_facets. This way one can later change this to be lazily evaluated.

Any thoughts?

[videlec]

comment:242

Replying to @kliem:

[...]

Please don't post messages waiting for an answer on a closed ticket. Discussion is closed. Open a new ticket and start a discussion there if something is wrong.