Opened 3 years ago

Closed 3 years ago

#27533 closed enhancement (fixed)

Improve Polyhedron.is_simple()

Reported by: gh-kliem Owned by:
Priority: minor Milestone: sage-8.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:

Status badges

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 gh-kliem

  • Branch set to public/27533
  • Commit set to bd10eb3e0d0ed2a2f2369dd2f6c63fd3166bc7e2
  • Status changed from new to needs_review

Last 10 new commits:

​3ec32e8Merge branch 'public/upgrade_polymake_to_version_3_2r2' of trac.sagemath.org:sage into new_24905
​f4dee94Updated polymake to 3.2r4
​d5b94d6Fixed quotes and wiggled around
​b2e133cFixed the typeof
​d9af561small fixes
​40c6098pep8
​a5bf869Fixed backend polymake
​7a5de5aMerge branch 'public/upgrade_polymake_to_version_3_2r4' of trac.sagemath.org:sage into polymake32r4
​606f53fMerge branch 'public/upgrade_polymake_to_version_3_2r4' of git://trac.sagemath.org/sage into develop
​bd10eb3Improved method ``is_simple``

comment:2 Changed 3 years ago by gh-kliem

  • Status changed from needs_review to needs_work

comment:3 Changed 3 years ago by git

  • Commit changed from bd10eb3e0d0ed2a2f2369dd2f6c63fd3166bc7e2 to f6aa8c6fca07ce99b2d9e7165525b30fa24c1396

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​392ca56Merge branch 'develop' of git://trac.sagemath.org/sage into develop
​f6aa8c6improved ``Polyhedron.is_simple()``

comment:4 Changed 3 years ago by git

  • Commit changed from f6aa8c6fca07ce99b2d9e7165525b30fa24c1396 to ec41ee175e7c3bc6c9a4a74aadf0ad754ab17667

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​ec41ee1improve is_simple

comment:5 Changed 3 years ago by gh-kliem

  • Branch changed from public/27533 to public/27533_new

comment:6 Changed 3 years ago by gh-kliem

  • Branch changed from public/27533_new to public/27533
  • Commit changed from ec41ee175e7c3bc6c9a4a74aadf0ad754ab17667 to cd714a1f21c3766ee87f2a28ddb8ee3f3552c9e1

Had to fix my git develop branch

New commits:

​cd714a1improved is_simple

comment:7 Changed 3 years ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:8 Changed 3 years ago by gh-kliem

  • Authors set to Jonathan Kliem

comment:9 Changed 3 years ago by gh-LaisRast

  • 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 gh-LaisRast

  • Reviewers set to Laith Rastanawi

comment:11 Changed 3 years ago by vbraun

  • 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.