Implement slack matrix for polyhedra

[kliem]

We implement the slack matrix for polyhedra.

This matrix contains all the evaluations of Hrepresentation elements on Vrepresentation elements.

This method can be used to obtain the incidence matrix much quicker (at least for base ring rationals or integers).

CC: @jplab @LaisRast

Component: geometry

Keywords: polyhedra, slack matrix

Author: Jonathan Kliem

Branch/Commit: 47a19c6

Reviewer: Matthias Koeppe

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

[kliem]

Branch: public/29838

[kliem]

Commit: 47a19c6

[kliem]

New commits:

47a19c6

implement slack matrix

[kliem]

comment:2

To obtain the slack matrix is currently much quicker than the incidence matrix:

sage: P = polytopes.permutahedron(7)
sage: %time M = P.slack_matrix()
CPU times: user 46.5 ms, sys: 4.06 ms, total: 50.6 ms
Wall time: 49.6 ms
sage: %time _ = P.incidence_matrix()
CPU times: user 684 ms, sys: 0 ns, total: 684 ms
Wall time: 683 ms

sage: P = polytopes.permutahedron(7)
sage: P = P.base_extend(QQ)
sage: %time M = P.slack_matrix()
CPU times: user 157 ms, sys: 4.01 ms, total: 161 ms
Wall time: 160 ms
sage: %time _ = P.incidence_matrix()
CPU times: user 1.2 s, sys: 17 µs, total: 1.2 s
Wall time: 1.2 s

sage: P = polytopes.associahedron(['A', 9])
sage: %time M = P.slack_matrix()
CPU times: user 312 ms, sys: 8 ms, total: 320 ms
Wall time: 319 ms
sage: %time _ = P.incidence_matrix()
CPU times: user 1.83 s, sys: 0 ns, total: 1.83 s
Wall time: 1.83 s

[mkoeppe]

comment:3

LGTM

[mkoeppe]

Reviewer: Matthias Koeppe

[vbraun]

Changed branch from public/29838 to 47a19c6