id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
28643 Speed up incidence matrix of polyhedra 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
}}}" enhancement closed major sage-9.0 geometry fixed polytopes, incidence matrix Jean-Philippe Labbé Laith Rastanawi Jonathan Kliem Laith Rastanawi N/A 6efb1bc7e06986126e8ba24da4ec9b7b6580be82 6efb1bc7e06986126e8ba24da4ec9b7b6580be82