#28643 closed enhancement (fixed)

Speed up incidence matrix of polyhedra

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.0
Component: geometry Keywords: polytopes, incidence matrix
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Laith Rastanawi
Report Upstream: N/A Work issues:
Branch: 6efb1bc (Commits, GitHub, GitLab) Commit: 6efb1bc7e06986126e8ba24da4ec9b7b6580be82
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-kliem)

We speed up the calculation of the incidence matrix by avoiding recomputation.

The obvious way to implement it, is by doing a nested loop (one loop for Vrepresentation, one for Hrepresentation). We do not change this. However, the inner loop should not recompute things, e.g.

  • the vector of a representation element,
  • the index of a representation element,
  • how to compute the product of two representation element (this consists of nested methods again), instead call the product of two vectors directly.

Before:

sage: P = polytopes.permutahedron(7)
sage: %time _ = P.incidence_matrix()
CPU times: user 2.21 s, sys: 52.4 ms, total: 2.26 s
Wall time: 2.21 s
sage: P = polytopes.associahedron(['A',10],backend='normaliz')
sage: %time _ = P.incidence_matrix()
CPU times: user 21.7 s, sys: 129 ms, total: 21.9 s
Wall time: 21.7 s

After:

sage: P = polytopes.permutahedron(7)
sage: %time _ = P.incidence_matrix()
CPU times: user 682 ms, sys: 81.4 ms, total: 764 ms
Wall time: 606 ms
sage: P = polytopes.associahedron(['A',10],backend='normaliz')
sage: %time _ = P.incidence_matrix()
CPU times: user 6.16 s, sys: 67.5 ms, total: 6.23 s
Wall time: 6.16 s

Change History (12)

comment:1 Changed 21 months ago by gh-kliem

  • Branch set to public/28643
  • Commit set to 0e419ebd40a1f393223ccd8afe8c44e71add67bc
  • Status changed from new to needs_review

New commits:

0e419eboptimized incidence matrix

comment:2 Changed 21 months ago by gh-kliem

  • Description modified (diff)

comment:3 Changed 21 months ago by gh-LaisRast

It is faster and still correct. One suggestion: I think it would be a good idea to add more examples in the docstring. For instance, you can add an example for unbounded polyhedron:

sage: P = Polyhedron(vertices=[(1,0,0), (1,1,0)], rays=[(1,0,0)], lines=[(0,0,1)])
sage: P.incidence_matrix()
[1 1 1]
[1 1 0]
[1 0 1]
[0 1 1]

comment:4 Changed 21 months ago by git

  • Commit changed from 0e419ebd40a1f393223ccd8afe8c44e71add67bc to e50590cea612d84a36e98bdb97d4f656c1f8b6dc

Branch pushed to git repo; I updated commit sha1. New commits:

e50590cmore examples to incidence matrix docstring

comment:5 Changed 21 months ago by gh-LaisRast

You wrote that "The incidence matrix is not unique up to permutation for unbounded polyhedra", I believe you meant something else.

Plus, it would be nice to include the following example (which you suggested before). This is an example of two "combinatorially isomorphic" polyhedra with different incidence matrices.

sage: P1 = Polyhedron(vertices=[[1,0],[-1,0]],rays=[[0,1]])
sage: P1.incidence_matrix()
[1 1 0]
[1 0 1]
[0 1 1]
sage: P2 = Polyhedron(vertices=[[1,0],[-1,0]],rays=[[0,1], [1,1]])
sage: P2.incidence_matrix()
[1 1 0]
[1 0 0]
[0 1 1]
[0 0 1]

comment:6 Changed 21 months ago by git

  • Commit changed from e50590cea612d84a36e98bdb97d4f656c1f8b6dc to a1738c81ecb018f6f4cfeda14caaf4fbdc7c8d19

Branch pushed to git repo; I updated commit sha1. New commits:

a1738c8improved examples

comment:7 Changed 21 months ago by gh-LaisRast

  • Reviewers set to Laith Rastanawi
  • Status changed from needs_review to positive_review

I think it is good to go.

comment:8 Changed 21 months ago by jipilab

  • Status changed from positive_review to needs_work

May I suggest:

-        The incidence matrix does not uniquely determine
-        an unbounded polyhedra::
+        An incidence matrix does not determine a unique 
+        polyhedra::

comment:9 Changed 21 months ago by git

  • Commit changed from a1738c81ecb018f6f4cfeda14caaf4fbdc7c8d19 to 6efb1bc7e06986126e8ba24da4ec9b7b6580be82

Branch pushed to git repo; I updated commit sha1. New commits:

6efb1bcimproved docstring

comment:10 Changed 21 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:11 Changed 21 months ago by gh-LaisRast

  • Status changed from needs_review to positive_review

comment:12 Changed 21 months ago by vbraun

  • Branch changed from public/28643 to 6efb1bc7e06986126e8ba24da4ec9b7b6580be82
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.