Opened 3 years ago
Closed 3 years ago
#28248 closed enhancement (fixed)
Add .boundary_complex() method for simplicial polytopes
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  geometry  Keywords:  polytopes, simplicial complex, days100 
Cc:  ghLaisRast, ghkliem, tscrim, jpalmieri  Merged in:  
Authors:  JeanPhilippe Labbé  Reviewers:  Laith Rastanawi 
Report Upstream:  N/A  Work issues:  
Branch:  7432567 (Commits, GitHub, GitLab)  Commit:  7432567611155c343490a16695f8d9f32a583ca6 
Dependencies:  #27974  Stopgaps: 
Description
The boundary of polytopes are nice and relatively wellbehaved 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 3 years ago by
 Dependencies set to #27974
comment:2 Changed 3 years ago by
 Branch set to u/jipilab/28248
 Commit set to 21ae4786d6e6e9ed654b827af9796a5b83771388
 Status changed from new to needs_review
comment:3 Changed 3 years ago by
 Commit changed from 21ae4786d6e6e9ed654b827af9796a5b83771388 to 890c350d596acfb0af7536f6c425083aceaf1bc9
comment:4 Changed 3 years ago by
comment:5 followup: ↓ 6 Changed 3 years ago by
 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 7permutahedron)
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 3 years ago by
Replying to ghLaisRast:
Since you only need the combinatorial data of the polytope, it would be much faster to use the
.incidence_matrix()
instead of the.faces()
(orfacets()
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.
comment:7 in reply to: ↑ 6 Changed 3 years ago by
Replying to ghkliem:
Replying to ghLaisRast:
Since you only need the combinatorial data of the polytope, it would be much faster to use the
.incidence_matrix()
instead of the.faces()
(orfacets()
here). (You can see the difference, for instance, clearly if you take the dual of the 7The 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))
vsP.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 followup: ↓ 9 Changed 3 years ago by
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 ; followup: ↓ 10 Changed 3 years ago by
Replying to ghkliem:
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 (inCombinatorialPolyhedron
) 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 3 years ago by
Replying to ghLaisRast:
Replying to ghkliem:
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 (inCombinatorialPolyhedron
) 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 ssage: 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 sMy 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 theincidence_matrix
instead offaces
.
+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 3 years ago by
 Commit changed from 890c350d596acfb0af7536f6c425083aceaf1bc9 to 388d7feb0c12c23845570be16ddf2e8aaff28716
Branch pushed to git repo; I updated commit sha1. New commits:
388d7fe  Changed to incidence matrix

comment:12 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:13 Changed 3 years ago by
 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 3 years ago by
 Milestone changed from sage8.9 to sagepending
comment:15 Changed 3 years ago by
 Milestone changed from sagepending to sage8.9
comment:16 Changed 3 years ago by
There's a small conflict due to the facets methods. I'll fix it.
comment:17 Changed 3 years ago by
 Status changed from positive_review to needs_work
comment:18 Changed 3 years ago by
 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
comment:19 Changed 3 years ago by
Rebased on sage8.9.rc0 and fixed conflict.
comment:20 Changed 3 years ago by
 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 3 years ago by
 Milestone changed from sage8.9 to sage9.0
moving milestone to 9.0 (after release of 8.9)
comment:22 Changed 3 years ago by
 Branch changed from u/jipilab/28248_v2 to 7432567611155c343490a16695f8d9f32a583ca6
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Added to quickref