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: | 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, GitHub, GitLab) | 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 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 follow-up: ↓ 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 7-permutahedron)
comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 3 years ago by
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()
(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 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()
(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))
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 follow-up: ↓ 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 ; follow-up: ↓ 10 Changed 3 years ago by
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 (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 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 (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 sage-8.9 to sage-pending
comment:15 Changed 3 years ago by
- Milestone changed from sage-pending to sage-8.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 sage-8.9 to sage-9.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