Add .boundary_complex() method for simplicial polytopes

[jplab]

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.

Depends on #27974

CC: @LaisRast @kliem @tscrim @jhpalmieri

Component: geometry

Keywords: polytopes, simplicial complex, days100

Author: Jean-Philippe Labbé

Branch: 7432567

Reviewer: Laith Rastanawi

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

[jplab]

Dependencies: #27974

[jplab]

Branch: u/jipilab/28248

[jplab]

Commit: 21ae478

[sagetrac-git]

Changed commit from 21ae478 to 890c350

[sagetrac-git]

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

890c350

Added to quickref

[sagetrac-coulbois]

Author: Jean-Philippe Labbé

[LaisRast]

comment:5

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)

[kliem]

comment:6

Replying to @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.

[LaisRast]

comment:7

Replying to @kliem:

Replying to @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.

[kliem]

comment:8

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).

[LaisRast]

comment:9

Replying to @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.

[jplab]

comment:10

Replying to @LaisRast:

Replying to @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.

[sagetrac-git]

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

388d7fe

Changed to incidence matrix

[sagetrac-git]

Changed commit from 890c350 to 388d7fe

[LaisRast]

Reviewer: Laith Rastanawi

[LaisRast]

comment:13

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.

[jplab]

comment:16

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

[jplab]

Changed branch from u/jipilab/28248 to u/jipilab/28248_v2

[jplab]

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

[jplab]

Changed commit from 388d7fe to 7432567

[jplab]

comment:19

Rebased on sage8.9.rc0 and fixed conflict.

[LaisRast]

comment:20

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

[fchapoton]

comment:21

moving milestone to 9.0 (after release of 8.9)

[vbraun]

Changed branch from u/jipilab/28248_v2 to 7432567

[fchapoton]

Changed commit from 7432567 to none