Opened 6 years ago
Closed 4 years ago
#22701 closed enhancement (fixed)
Setting up a Polyhedron from both Vrep and Hrep  for backend='field'
Reported by:  Matthias Köppe  Owned by:  

Priority:  major  Milestone:  sage8.4 
Component:  geometry  Keywords:  polytope, geometry, days84 
Cc:  JeanPhilippe Labbé, Marcelo Forets, Moritz Firsching, Andrey Novoseltsev, Travis Scrimshaw  Merged in:  
Authors:  Matthias Koeppe  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  e34d845 (Commits, GitHub, GitLab)  Commit:  e34d84523dbb0602c1ca73d6ea3a59bb79f66425 
Dependencies:  Stopgaps: 
Description (last modified by )
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 Vrep and Hrep are given, they must be minimal; the interface is designed to allow for future extensions.
The toplevel 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 6dimensional 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
Followup:
Change History (14)
comment:1 Changed 6 years ago by
Description:  modified (diff) 

comment:2 Changed 6 years ago by
Cc:  Moritz Firsching added 

comment:3 Changed 6 years ago by
Cc:  Andrey Novoseltsev added 

comment:4 Changed 6 years ago by
comment:5 Changed 6 years ago by
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.
comment:6 Changed 4 years ago by
Branch:  → u/mkoeppe/setting_up_a_polyhedron_from_both_vrep_and_hrep 

comment:7 Changed 4 years ago by
Authors:  → Matthias Koeppe 

Cc:  Travis Scrimshaw added 
Commit:  → 6d91f255cacaf7fb89b3a8ad1ebcc470e7ef7437 
Description:  modified (diff) 
Milestone:  sage8.0 → sage8.4 
Status:  new → needs_review 
Summary:  Setting up a Polyhedron from both Vrep and Hrep → Setting up a Polyhedron from both Vrep and Hrep  for backend='field' 
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

comment:8 Changed 4 years ago by
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
comment:9 Changed 4 years ago by
Commit:  6d91f255cacaf7fb89b3a8ad1ebcc470e7ef7437 → e34d84523dbb0602c1ca73d6ea3a59bb79f66425 

Branch pushed to git repo; I updated commit sha1. New commits:
e34d845  Polyhedron_field.__init__: Reword error message, add docstring

comment:10 Changed 4 years ago by
(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.)
comment:11 Changed 4 years ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → positive_review 
Thanks.
comment:13 Changed 4 years ago by
Description:  modified (diff) 

comment:14 Changed 4 years ago by
Branch:  u/mkoeppe/setting_up_a_polyhedron_from_both_vrep_and_hrep → e34d84523dbb0602c1ca73d6ea3a59bb79f66425 

Resolution:  → fixed 
Status:  positive_review → closed 
in another software you can instantiate a polyhedron with "just" the hrep (or vrep), and compute the complementary representation ondemand. 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.