Opened 8 months ago

Closed 6 months ago

#28248 closed enhancement (fixed)

Add .boundary_complex() method for simplicial polytopes

Reported by: jipilab Owned by:
Priority: major Milestone: sage-9.0
Component: geometry Keywords: polytopes, simplicial complex, days100
Cc: gh-LaisRast, gh-kliem, tscrim, jpalmieri Merged in:
Authors: Jean-Philippe Labbé Reviewers: Laith Rastanawi
Report Upstream: N/A Work issues:
Branch: 7432567 (Commits) Commit: 7432567611155c343490a16695f8d9f32a583ca6
Dependencies: #27974 Stopgaps:

Description

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.

Change History (22)

comment:1 Changed 8 months ago by jipilab

  • Dependencies set to #27974

comment:2 Changed 8 months ago by jipilab

  • Branch set to u/jipilab/28248
  • Commit set to 21ae4786d6e6e9ed654b827af9796a5b83771388
  • Status changed from new to needs_review

comment:3 Changed 8 months ago by git

  • Commit changed from 21ae4786d6e6e9ed654b827af9796a5b83771388 to 890c350d596acfb0af7536f6c425083aceaf1bc9

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

890c350Added to quickref

comment:4 Changed 8 months ago by coulbois

  • Authors set to Jean-Philippe Labbé

comment:5 follow-up: Changed 8 months ago by gh-LaisRast

  • Status changed from needs_review to needs_work

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)

comment:6 in reply to: ↑ 5 ; follow-up: Changed 8 months ago by 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.

Last edited 8 months ago by gh-kliem (previous) (diff)

comment:7 in reply to: ↑ 6 Changed 8 months ago by 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.

comment:8 follow-up: Changed 8 months ago by 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).

comment:9 in reply to: ↑ 8 ; follow-up: Changed 8 months ago by 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.

comment:10 in reply to: ↑ 9 Changed 8 months ago by 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.

comment:11 Changed 8 months ago by git

  • Commit changed from 890c350d596acfb0af7536f6c425083aceaf1bc9 to 388d7feb0c12c23845570be16ddf2e8aaff28716

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

388d7feChanged to incidence matrix

comment:12 Changed 8 months ago by jipilab

  • Status changed from needs_work to needs_review

comment:13 Changed 8 months ago by gh-LaisRast

  • Reviewers set to Laith Rastanawi
  • Status changed from needs_review to positive_review

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.

comment:14 Changed 8 months ago by chapoton

  • Milestone changed from sage-8.9 to sage-pending

comment:15 Changed 7 months ago by chapoton

  • Milestone changed from sage-pending to sage-8.9

comment:16 Changed 7 months ago by jipilab

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

comment:17 Changed 7 months ago by jipilab

  • Status changed from positive_review to needs_work

comment:18 Changed 7 months ago by jipilab

  • Branch changed from u/jipilab/28248 to u/jipilab/28248_v2
  • Commit changed from 388d7feb0c12c23845570be16ddf2e8aaff28716 to 7432567611155c343490a16695f8d9f32a583ca6
  • Status changed from needs_work to needs_review

New commits:

fbc3ad3First version
877eaa5added cross-references, changed faces examples to facets where appropriate
6457c02Added examples
112c30ffixed tests
e6fe7a8Added to quickref
7432567Changed to incidence matrix

comment:19 Changed 7 months ago by jipilab

Rebased on sage8.9.rc0 and fixed conflict.

comment:20 Changed 7 months ago by gh-LaisRast

  • Status changed from needs_review to positive_review

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

comment:21 Changed 6 months ago by chapoton

  • Milestone changed from sage-8.9 to sage-9.0

moving milestone to 9.0 (after release of 8.9)

comment:22 Changed 6 months ago by vbraun

  • Branch changed from u/jipilab/28248_v2 to 7432567611155c343490a16695f8d9f32a583ca6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.