#29841 closed enhancement (fixed)

Improve obtaining combinatorial polyhedron

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.2
Component: geometry Keywords: combinatorial polyhedron
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 2db3a70 (Commits, GitHub, GitLab) Commit: 2db3a70c8f39d1fead1b1fdf34422167a827a8e9
Dependencies: #29837 Stopgaps:

Status badges

Description (last modified by gh-kliem)

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 14 months ago by gh-kliem

  • Branch set to public/29841
  • Status changed from new to needs_review

comment:2 Changed 14 months ago by git

  • Commit set to 464f5c5161082dd34095415741d1e13c86ddb3ff

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

7b70830rename
47a19c6implement slack matrix
54755d7Merge branch 'public/29838' of git://trac.sagemath.org/sage into public/29837-reb
a4576d6set up incidence/adjacency matrix with GF(2)
30c4715Merge branch 'public/29840' of git://trac.sagemath.org/sage into public/29837-reb
fcd62d2determine is_zero beforehand
13b8583small fix
89aeab3obtain incidence matrix from slack matrix
d8e4153improve initialization of CombinatorialPolyhedron
464f5c5reobtain incidence matrix more quickly

comment:3 Changed 14 months ago by gh-kliem

  • Status changed from needs_review to needs_work

comment:4 Changed 14 months ago by gh-kliem

  • Branch changed from public/29841 to public/29841-reb
  • Commit changed from 464f5c5161082dd34095415741d1e13c86ddb3ff to addee643b8fe9964ac37111560095d8a57086910
  • Description modified (diff)
  • Status changed from needs_work to needs_review

New commits:

62f1ff9use integer matrix for zero_pattern_matrix
88f6025Merge branch 'public/29838' of git://trac.sagemath.org/sage into public/29837-reb2
7cee020determine is_zero beforehand
3d28d09small fix
7ef6a11use slack matrix to obtain incidence matrix quicker
7ff9f92improve initialization of CombinatorialPolyhedron
20d22a8mod2 -> integer; improve reobtainment of incidence matrix
addee64do not delete columns if we do not have to

comment:5 Changed 14 months ago by gh-kliem

  • Branch changed from public/29841-reb to public/29841-reb2
  • Commit changed from addee643b8fe9964ac37111560095d8a57086910 to 2db3a70c8f39d1fead1b1fdf34422167a827a8e9
  • Description modified (diff)

Last 10 new commits:

2a08abesmall mistakes
333c4bawrong doctest
82c6b4adocstring
211f4f1Merge branch 'public/29839' of git://trac.sagemath.org/sage into public/29837-reb3
4c5433edetermine is_zero beforehand
27a1b90use slack matrix to obtain incidence matrix quicker
764a99baccount for change in #29839
1b654c4improve initialization of CombinatorialPolyhedron
527316dmod2 -> integer; improve reobtainment of incidence matrix
2db3a70do not delete columns if we do not have to

comment:6 Changed 13 months ago by gh-kliem

  • Description modified (diff)

comment:7 Changed 13 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:8 Changed 13 months ago by gh-kliem

Thank you.

comment:9 Changed 13 months ago by vbraun

  • Branch changed from public/29841-reb2 to 2db3a70c8f39d1fead1b1fdf34422167a827a8e9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.