Speed up incidence matrix of polyhedra

[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

CC: @jplab @LaisRast

Component: geometry

Keywords: polytopes, incidence matrix

Author: Jonathan Kliem

Branch/Commit: 6efb1bc

Reviewer: Laith Rastanawi

Issue created by migration from https://trac.sagemath.org/ticket/28643

[kliem]

Commit: 0e419eb

[kliem]

New commits:

0e419eb

optimized incidence matrix

[kliem]

Branch: public/28643

[kliem]

Description changed:

--- 
+++ 
@@ -1,4 +1,12 @@
 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:
 

[LaisRast]

comment:3

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]

[sagetrac-git]

Changed commit from 0e419eb to e50590c

[sagetrac-git]

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

e50590c

more examples to incidence matrix docstring

[LaisRast]

comment:5

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]

[sagetrac-git]

Changed commit from e50590c to a1738c8

[sagetrac-git]

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

a1738c8

improved examples