Setting up a Polyhedron from both Vrep and Hrep - for backend='field'

[mkoeppe]

Currently, only one of the two is allowed.
For at least some backends (certainly, the generic ("field") backend and polymake (#22683)), it makes sense to initialize with both if they are known, to avoid expensive recomputation. (This could also be the basis of code that delegates to a particular backend for particular features.)
Users should also be allowed to indicate whether the given presentations are already minimal.

In this ticket, we implement this for Polyhedron_field, enabling fast base_extend.

When both V-rep and H-rep are given, they must be minimal; the interface is designed to allow for future extensions.

The top-level constructor Polyhedron is unchanged in this ticket. It is still an error if Polyhedron(vertices=..., inequalities=...) is attempted.

Without this ticket:

sage: p = polytopes.hypercube(6, backend='ppl')
sage: %time q = p.base_extend(AA)
CPU times: user 2.27 s, sys: 10.3 ms, total: 2.28 s
Wall time: 2.28 s
sage: q
A 6-dimensional polyhedron in AA^6 defined as the convex hull of 64 vertices

With this ticket:

CPU times: user 13.4 ms, sys: 603 µs, total: 14 ms
Wall time: 14.9 ms

Related:

• Polyhedron class mistreats empty inputs #17339: Polyhedron class mistreats empty inputs

Follow-up:

• Setting up a Polyhedron from both Vrep and Hrep - for backend='polymake' #26368: Setting up a Polyhedron from both Vrep and Hrep - for backend='polymake'
• Polyhedron constructors: minimal vs. non-minimal input representations; input both Vrep and Hrep #26366: Polyhedron - lazy backend; minimal vs. non-minimal presentations; Polyhedron constructor with both Vrep, Hrep

CC: @jplab @mforets @mo271 @novoselt @tscrim

Component: geometry

Keywords: polytope, days84

Author: Matthias Koeppe

Branch/Commit: e34d845

Reviewer: Travis Scrimshaw

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

[mkoeppe]

Description changed:

--- 
+++ 
@@ -4,4 +4,5 @@
 
 In particular this could help to implement a fast version of `change_backend()` (#22575) and could be the basis of code that delegates to a particular backend for particular features.
 
-
+Related: 
+- #17339: Polyhedron class mistreats empty inputs

[mforets]

comment:4

in another software you can instantiate a polyhedron with "just" the h-rep (or v-rep), and compute the complementary representation on-demand. this is useful especially when you work in high dimensions, and makes sense because there are questions which only rely on having just one representation.

so i wonder if this can be considered in this ticket, something like a keyword argument compute_complementary_representation which is true by default, to cover those use cases.

[mkoeppe]

comment:5

I think we could have a separate "lazy" backend that can only hold a given Hrep or Vrep. Whenever anything needs to be computed that requires the other representation, one could change to an actual backend.

[mkoeppe]

Branch: u/mkoeppe/setting_up_a_polyhedron_from_both_vrep_and_hrep

[mkoeppe]

Commit: 6d91f25

[mkoeppe]

Author: Matthias Koeppe

[mkoeppe]

New commits:

cc73721	Polyhedron_field._init_{H,V}representation_backend: Refactor through new methods _init_{H,V}representation
7a0438e	Polyhedra_base._element_constructor: Refactor through new method _element_constructor_polyhedron
d6e0d68	Polyhedra_field._element_constructor: Implement a version using both representations
6d91f25	Polyhedron_field.__init__: New, handle Vrep+Hrep case

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,8 +1,31 @@
 Currently, only one of the two is allowed.
-For at least some backends (certainly, the generic (`"field"`) backend and polymake (#22683)), it makes sense to initialize with both if they are known, to avoid expensive recomputation. 
+For at least some backends (certainly, the generic (`"field"`) backend and polymake (#22683)), it makes sense to initialize with both if they are known, to avoid expensive recomputation.  (This could also be the basis of code that delegates to a particular backend for particular features.)
 Users should also be allowed to indicate whether the given presentations are already minimal.
 
-In particular this could help to implement a fast version of `change_backend()` (#22575) and could be the basis of code that delegates to a particular backend for particular features.
+In this ticket, we implement this for `Polyhedron_field`, enabling fast `base_extend`.
+
+When both V-rep and H-rep are given, they must be minimal; the interface is designed to allow for future extensions.
+
+The top-level constructor `Polyhedron` is unchanged in this ticket. It is still an error if `Polyhedron(vertices=..., inequalities=...)` is attempted. 
+
+Without this ticket:
+
+```
+sage: p = polytopes.hypercube(6, backend='ppl')
+sage: %time q = p.base_extend(AA)
+CPU times: user 2.27 s, sys: 10.3 ms, total: 2.28 s
+Wall time: 2.28 s
+sage: q
+A 6-dimensional polyhedron in AA^6 defined as the convex hull of 64 vertices
+```
+
+With this ticket:
+
+```
+CPU times: user 13.4 ms, sys: 603 µs, total: 14 ms
+Wall time: 14.9 ms
+```
+
 
 Related: 
 - #17339: Polyhedron class mistreats empty inputs

[tscrim]

comment:8

One little thing:

-raise ValueError("If both Vrep and Hrep are provided, they must be minimal and Vrep_minimal and Hrep_minimal must be set True to indicate this.")
+raise ValueError("if both Vrep and Hrep are provided, they must be minimal"
                  " and Vrep_minimal and Hrep_minimal must both be True")

Otherwise LGTM.

---

One good way to do things lazily is use the @lazy_attribute. It also works well when setting self._foo = x.

sage: class Foo(object):
....:     @lazy_attribute
....:     def test(self):
....:         return [x for x in WeylGroup(['E',8],prefix='s')]
....:     
sage: F = Foo()
sage: F.test = 5
sage: F.test
5
sage: B = Foo()
sage: B.test  # This will take a while

[sagetrac-git]

Changed commit from 6d91f25 to e34d845

[sagetrac-git]

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

e34d845

Polyhedron_field.__init__: Reword error message, add docstring

[mkoeppe]

comment:10

(Thanks for the info on lazy_attribute. I've opened ticket #26366 for possible discussion of a lazy backend; but I do not plan to work on it.)

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:11

Thanks.