Add .boundary_complex() method for simplicial polytopes

[jipilab]

The boundary of polytopes are nice and relatively well-behaved cell complexes.

When the polytope is simplicial, its boundary is a simplicial complex. This ticket implements a method to return that simplicial complex.

[git]

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

​890c350

Added to quickref

[gh-LaisRast]

Since you only need the combinatorial data of the polytope, it would be much faster to use the .incidence_matrix() instead of the .faces() (or facets() here). (You can see the difference, for instance, clearly if you take the dual of the 7-permutahedron)

[gh-kliem]

Replying to gh-LaisRast:

Since you only need the combinatorial data of the polytope, it would be much faster to use the .incidence_matrix() instead of the .faces() (or facets() here). (You can see the difference, for instance, clearly if you take the dual of the 7-

The difference will only be minor, once #27063 is done. It's still going to be faster to just take the incidence matrix, but not by much.

Try it out tuple(CombinatorialPolyhedron(P).face_iter(P.dimension()-1)) vs P.incidence_matrix().

Be aware that the incidence matrix is cashed.

[gh-LaisRast]

Replying to gh-kliem:

Replying to gh-LaisRast:

Since you only need the combinatorial data of the polytope, it would be much faster to use the .incidence_matrix() instead of the .faces() (or facets() here). (You can see the difference, for instance, clearly if you take the dual of the 7-

The difference will only be minor, once #27063 is done. It's still going to be faster to just take the incidence matrix, but not by much.

Try it out tuple(CombinatorialPolyhedron(P).face_iter(P.dimension()-1)) vs P.incidence_matrix().

Be aware that the incidence matrix is cashed.

Actually no. Running CombinatorialPolyhedron(P) will compute the incidence matrix of P to initialize the CombinatorialPolyhedron. P.incidence_matrix() is still far faster.

[gh-kliem]

I know that it will compute the incidence matrix anyway. However, I disagree that it is far faster. Almost all the time initializing CombinatorialPolyhedron is spent on the incidence matrix. To obtain all the facets (in CombinatorialPolyhedron) is really quick, because there is nothing to compute anymore.

Overall, I don't think your suggested change is going to make a big difference (yes it will be slightly faster).

[gh-LaisRast]

Replying to gh-kliem:

I know that it will compute the incidence matrix anyway. However, I disagree that it is far faster. Almost all the time initializing CombinatorialPolyhedron is spent on the incidence matrix. To obtain all the facets (in CombinatorialPolyhedron) is really quick, because there is nothing to compute anymore.

Overall, I don't think your suggested change is going to make a big difference (yes it will be slightly faster).

For the Polyhedron class (which this method is implemented for), you can see that there is a big difference.

For your suggested method:

sage: P = polytopes.permutahedron(7)
sage: %time I = P.incidence_matrix()
CPU times: user 2.85 s, sys: 72.4 ms, total: 2.92 s
Wall time: 2.83 s

sage: Q = polytopes.permutahedron(7)
sage: %time I = tuple(CombinatorialPolyhedron(Q).face_iter(Q.dimension()-1))
CPU times: user 3.99 s, sys: 287 ms, total: 4.28 s
Wall time: 3.98 s

My suggested change is still faster since it computes less.

Anyway, since #27063 is not yet done, and since the class is Polyhedron, there is a big difference in using the incidence_matrix instead of faces.

[jipilab]

Replying to gh-LaisRast:

Replying to gh-kliem:

I know that it will compute the incidence matrix anyway. However, I disagree that it is far faster. Almost all the time initializing CombinatorialPolyhedron is spent on the incidence matrix. To obtain all the facets (in CombinatorialPolyhedron) is really quick, because there is nothing to compute anymore.

Overall, I don't think your suggested change is going to make a big difference (yes it will be slightly faster).

For the Polyhedron class (which this method is implemented for), you can see that there is a big difference.

For your suggested method:

sage: P = polytopes.permutahedron(7)
sage: %time I = P.incidence_matrix()
CPU times: user 2.85 s, sys: 72.4 ms, total: 2.92 s
Wall time: 2.83 s

sage: Q = polytopes.permutahedron(7)
sage: %time I = tuple(CombinatorialPolyhedron(Q).face_iter(Q.dimension()-1))
CPU times: user 3.99 s, sys: 287 ms, total: 4.28 s
Wall time: 3.98 s

My suggested change is still faster since it computes less.

Anyway, since #27063 is not yet done, and since the class is Polyhedron, there is a big difference in using the incidence_matrix instead of faces.

+1

I will replace to incidence_matrix. Once #27063 is done, the discussion may resume and check what is best, for now, incidence_matrix does the job.

[git]

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

​388d7fe

Changed to incidence matrix

[gh-LaisRast]

Beside the implementaion of facets method, which is going to be taken care of in #27974, the code looks good to me. The tests seem to pass on my machine and on the patchbot. Thus, I will consider this as a positive review.

[jipilab]

There's a small conflict due to the facets methods. I'll fix it.

[jipilab]

New commits:

​fbc3ad3	First version
​877eaa5	added cross-references, changed faces examples to facets where appropriate
​6457c02	Added examples
​112c30f	fixed tests
​e6fe7a8	Added to quickref
​7432567	Changed to incidence matrix

[jipilab]

Rebased on sage8.9.rc0 and fixed conflict.

[gh-LaisRast]

Since the conflict is now resolved, I will put the ticket on positive review again.

[chapoton]

moving milestone to 9.0 (after release of 8.9)