Implement adding generators or constraints to ppl polyhedron

[kliem]

Depends on #33666
Depends on #33678
Depends on #33679

CC: @jplab @mkoeppe @yuan-zhou

Component: geometry

Author: Jonathan Kliem

Branch/Commit: u/gh-kliem/adding_generators_constraints_ppl @ 1a00137

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

[kliem]

comment:1

I think at this point one should discuss, whether the suggested names and approach are good.

• The decorator _modification_method is a bit complicated, but it might make future methods easier.
  E.g. we can easily implement

@_modification_method
def intersection(self, other):
    self._add_constraints(other.inequality_generator(), other.equation_generator())

(Actually we need to name this something as _intersection and then call _intersection from Polyhedron_base5.intersection, because this is a modification method.

• Do we want the same methods in Polyhedron_base as well. Something like add_vertex (which should probably throw and error if called with inplace=True).
• What should happen if the base ring is wrong. Are we trying to catch this or not? E.g. what should P.intersection(Q, inplace=True) do for a mutable polyhedron P.

Use cases:

• If I implement intersection as suggested above, I already get a 10 percent improvement when running the benchmarks from Some optimizations for method regions of hyperplane arrangements #29661.

sage: %time P = polytopes.hypercube(10)
CPU times: user 46.8 ms, sys: 0 ns, total: 46.8 ms
Wall time: 46.1 ms
sage: %time Q = 2*polytopes.cross_polytope(10)
CPU times: user 102 ms, sys: 0 ns, total: 102 ms
Wall time: 101 ms
sage: %time P.intersection(Q)
CPU times: user 6.87 s, sys: 3.95 ms, total: 6.87 s
Wall time: 6.87 s
A 10-dimensional polyhedron in ZZ^10 defined as the convex hull of 180 vertices
sage: %time Q.intersection(P)
CPU times: user 6.9 s, sys: 3.97 ms, total: 6.91 s
Wall time: 6.91 s
A 10-dimensional polyhedron in ZZ^10 defined as the convex hull of 180 vertices
sage: %time P.add_Hrepresentatives(Q.inequality_generator(), Q.equation_generator())
CPU times: user 3.76 s, sys: 0 ns, total: 3.76 s
Wall time: 3.76 s
A 10-dimensional polyhedron in ZZ^10 defined as the convex hull of 180 vertices
sage: %time Q.add_Hrepresentatives(P.inequality_generator(), P.equation_generator())
CPU times: user 114 ms, sys: 7 µs, total: 114 ms
Wall time: 113 ms
A 10-dimensional polyhedron in ZZ^10 defined as the convex hull of 180 vertices

This will improve intersection and convex hull.
Note that we only expose something, the backend is already capable of.
But the advantage would be, that the user does not have to worry about it.