Opened 2 years ago
Closed 2 years ago
#29841 closed enhancement (fixed)
Improve obtaining combinatorial polyhedron
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  geometry  Keywords:  combinatorial polyhedron 
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  2db3a70 (Commits, GitHub, GitLab)  Commit:  2db3a70c8f39d1fead1b1fdf34422167a827a8e9 
Dependencies:  #29837  Stopgaps: 
Description (last modified by )
This ticket improves obtaining the CombinatorialPolyhedron
from an incidence matrix.
Along the way we also improve the method CombinatorialPolyhedron.incidence_matrix
that reobtains the incidence matrix.
Note that #29837 greatly speeds up obtainment of incidence matrices in Polyhedron_base
.
Without this ticket:
sage: P = polytopes.permutahedron(7) sage: _ = P.incidence_matrix() sage: %time C = CombinatorialPolyhedron(P) CPU times: user 821 ms, sys: 19.4 ms, total: 840 ms Wall time: 842 ms sage: C.incidence_matrix.clear_cache() sage: %time _ = C.incidence_matrix() CPU times: user 24.8 ms, sys: 22 µs, total: 24.8 ms Wall time: 24.6 ms sage: P = polytopes.associahedron(['A', 9]) sage: _ = P.incidence_matrix() sage: %time C = CombinatorialPolyhedron(P) CPU times: user 1.08 s, sys: 36.1 ms, total: 1.11 s Wall time: 1.11 s sage: C.incidence_matrix.clear_cache() sage: %time _ = C.incidence_matrix() CPU times: user 94.2 ms, sys: 0 ns, total: 94.2 ms Wall time: 93.8 ms
With this ticket:
sage: P = polytopes.permutahedron(7) sage: _ = P.incidence_matrix() sage: %time C = CombinatorialPolyhedron(P) CPU times: user 77.6 ms, sys: 12 ms, total: 89.6 ms Wall time: 88 ms sage: C.incidence_matrix.clear_cache() sage: %time _ = C.incidence_matrix() CPU times: user 17 ms, sys: 14 µs, total: 17 ms Wall time: 16.7 ms sage: P = polytopes.associahedron(['A', 9]) sage: _ = P.incidence_matrix() sage: %time C = CombinatorialPolyhedron(P) CPU times: user 110 ms, sys: 0 ns, total: 110 ms Wall time: 109 ms sage: C.incidence_matrix.clear_cache() sage: %time _ = C.incidence_matrix() CPU times: user 65.3 ms, sys: 18 µs, total: 65.3 ms Wall time: 64.3 ms
Change History (9)
comment:1 Changed 2 years ago by
 Branch set to public/29841
 Status changed from new to needs_review
comment:2 Changed 2 years ago by
 Commit set to 464f5c5161082dd34095415741d1e13c86ddb3ff
comment:3 Changed 2 years ago by
 Status changed from needs_review to needs_work
comment:4 Changed 2 years ago by
 Branch changed from public/29841 to public/29841reb
 Commit changed from 464f5c5161082dd34095415741d1e13c86ddb3ff to addee643b8fe9964ac37111560095d8a57086910
 Description modified (diff)
 Status changed from needs_work to needs_review
New commits:
62f1ff9  use integer matrix for zero_pattern_matrix

88f6025  Merge branch 'public/29838' of git://trac.sagemath.org/sage into public/29837reb2

7cee020  determine is_zero beforehand

3d28d09  small fix

7ef6a11  use slack matrix to obtain incidence matrix quicker

7ff9f92  improve initialization of CombinatorialPolyhedron

20d22a8  mod2 > integer; improve reobtainment of incidence matrix

addee64  do not delete columns if we do not have to

comment:5 Changed 2 years ago by
 Branch changed from public/29841reb to public/29841reb2
 Commit changed from addee643b8fe9964ac37111560095d8a57086910 to 2db3a70c8f39d1fead1b1fdf34422167a827a8e9
 Description modified (diff)
Last 10 new commits:
2a08abe  small mistakes

333c4ba  wrong doctest

82c6b4a  docstring

211f4f1  Merge branch 'public/29839' of git://trac.sagemath.org/sage into public/29837reb3

4c5433e  determine is_zero beforehand

27a1b90  use slack matrix to obtain incidence matrix quicker

764a99b  account for change in #29839

1b654c4  improve initialization of CombinatorialPolyhedron

527316d  mod2 > integer; improve reobtainment of incidence matrix

2db3a70  do not delete columns if we do not have to

comment:6 Changed 2 years ago by
 Description modified (diff)
comment:7 Changed 2 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
LGTM.
comment:8 Changed 2 years ago by
Thank you.
comment:9 Changed 2 years ago by
 Branch changed from public/29841reb2 to 2db3a70c8f39d1fead1b1fdf34422167a827a8e9
 Resolution set to fixed
 Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
rename
implement slack matrix
Merge branch 'public/29838' of git://trac.sagemath.org/sage into public/29837reb
set up incidence/adjacency matrix with GF(2)
Merge branch 'public/29840' of git://trac.sagemath.org/sage into public/29837reb
determine is_zero beforehand
small fix
obtain incidence matrix from slack matrix
improve initialization of CombinatorialPolyhedron
reobtain incidence matrix more quickly