Opened 3 years ago
Closed 3 years ago
#27533 closed enhancement (fixed)
Improve Polyhedron.is_simple()
Reported by:  ghkliem  Owned by:  

Priority:  minor  Milestone:  sage8.8 
Component:  geometry  Keywords:  
Cc:  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Laith Rastanawi 
Report Upstream:  N/A  Work issues:  
Branch:  cd714a1 (Commits, GitHub, GitLab)  Commit:  cd714a1f21c3766ee87f2a28ddb8ee3f3552c9e1 
Dependencies:  Stopgaps: 
Description
The method Polyhedron.is_simple
is pretty slow for large polytopes at the moment. There is no need for that, as the information can be directly retrieved from the Vrepresentation
.
Current timings:
sage: P = polytopes.hypercube(6) sage: %time P.is_simple() CPU times: user 360 ms, sys: 8 ms, total: 368 ms Wall time: 364 ms True sage: P = polytopes.hypercube(7) sage: %time P.is_simple() CPU times: user 1.78 s, sys: 48 ms, total: 1.83 s Wall time: 1.74 s True sage: P = polytopes.cross_polytope(7) sage: %time P.is_simple() CPU times: user 996 ms, sys: 0 ns, total: 996 ms Wall time: 992 ms False
Timings with this ticket:
sage: P = polytopes.hypercube(6) sage: %time P.is_simple() CPU times: user 4 ms, sys: 4 ms, total: 8 ms Wall time: 3.53 ms True sage: P = polytopes.hypercube(7) sage: %time P.is_simple() CPU times: user 4 ms, sys: 4 ms, total: 8 ms Wall time: 5.39 ms True sage: P = polytopes.cross_polytope(7) sage: %time P.is_simple() CPU times: user 8 ms, sys: 0 ns, total: 8 ms Wall time: 5.63 ms False sage: P = polytopes.permutahedron(4) sage: %time P.is_simple() CPU times: user 0 ns, sys: 0 ns, total: 0 ns Wall time: 1.03 ms True
Change History (11)
comment:1 Changed 3 years ago by
 Branch set to public/27533
 Commit set to bd10eb3e0d0ed2a2f2369dd2f6c63fd3166bc7e2
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:3 Changed 3 years ago by
 Commit changed from bd10eb3e0d0ed2a2f2369dd2f6c63fd3166bc7e2 to f6aa8c6fca07ce99b2d9e7165525b30fa24c1396
comment:4 Changed 3 years ago by
 Commit changed from f6aa8c6fca07ce99b2d9e7165525b30fa24c1396 to ec41ee175e7c3bc6c9a4a74aadf0ad754ab17667
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ec41ee1  improve is_simple

comment:5 Changed 3 years ago by
 Branch changed from public/27533 to public/27533_new
comment:6 Changed 3 years ago by
 Branch changed from public/27533_new to public/27533
 Commit changed from ec41ee175e7c3bc6c9a4a74aadf0ad754ab17667 to cd714a1f21c3766ee87f2a28ddb8ee3f3552c9e1
comment:7 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:8 Changed 3 years ago by
comment:9 Changed 3 years ago by
 Status changed from needs_review to positive_review
This is much faster than the previous way. It looks fine to me.
comment:10 Changed 3 years ago by
 Reviewers set to Laith Rastanawi
comment:11 Changed 3 years ago by
 Branch changed from public/27533 to cd714a1f21c3766ee87f2a28ddb8ee3f3552c9e1
 Resolution set to fixed
 Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
Last 10 new commits:
Merge branch 'public/upgrade_polymake_to_version_3_2r2' of trac.sagemath.org:sage into new_24905
Updated polymake to 3.2r4
Fixed quotes and wiggled around
Fixed the typeof
small fixes
pep8
Fixed backend polymake
Merge branch 'public/upgrade_polymake_to_version_3_2r4' of trac.sagemath.org:sage into polymake32r4
Merge branch 'public/upgrade_polymake_to_version_3_2r4' of git://trac.sagemath.org/sage into develop
Improved method ``is_simple``