Opened 21 months ago
Closed 21 months ago
#28643 closed enhancement (fixed)
Speed up incidence matrix of polyhedra
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  geometry  Keywords:  polytopes, incidence matrix 
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Laith Rastanawi 
Report Upstream:  N/A  Work issues:  
Branch:  6efb1bc (Commits, GitHub, GitLab)  Commit:  6efb1bc7e06986126e8ba24da4ec9b7b6580be82 
Dependencies:  Stopgaps: 
Description (last modified by )
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
 Branch set to public/28643
 Commit set to 0e419ebd40a1f393223ccd8afe8c44e71add67bc
 Status changed from new to needs_review
comment:2 Changed 21 months ago by
 Description modified (diff)
comment:3 Changed 21 months ago by
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
 Commit changed from 0e419ebd40a1f393223ccd8afe8c44e71add67bc to e50590cea612d84a36e98bdb97d4f656c1f8b6dc
Branch pushed to git repo; I updated commit sha1. New commits:
e50590c  more examples to incidence matrix docstring

comment:5 Changed 21 months ago by
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
 Commit changed from e50590cea612d84a36e98bdb97d4f656c1f8b6dc to a1738c81ecb018f6f4cfeda14caaf4fbdc7c8d19
Branch pushed to git repo; I updated commit sha1. New commits:
a1738c8  improved examples

comment:7 Changed 21 months ago by
 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
 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
 Commit changed from a1738c81ecb018f6f4cfeda14caaf4fbdc7c8d19 to 6efb1bc7e06986126e8ba24da4ec9b7b6580be82
Branch pushed to git repo; I updated commit sha1. New commits:
6efb1bc  improved docstring

comment:10 Changed 21 months ago by
 Status changed from needs_work to needs_review
comment:11 Changed 21 months ago by
 Status changed from needs_review to positive_review
comment:12 Changed 21 months ago by
 Branch changed from public/28643 to 6efb1bc7e06986126e8ba24da4ec9b7b6580be82
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
optimized incidence matrix