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: sage-8.4
Component: geometry Keywords: polytope, geometry, days84
Cc: Jean-Philippe 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:

Status badges

Description (last modified by Matthias Köppe)

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:

  • #17339: Polyhedron class mistreats empty inputs

Follow-up:

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

Change History (14)

comment:1 Changed 6 years ago by Matthias Köppe

Description: modified (diff)

comment:2 Changed 6 years ago by Moritz Firsching

Cc: Moritz Firsching added

comment:3 Changed 6 years ago by Andrey Novoseltsev

Cc: Andrey Novoseltsev added

comment:4 Changed 6 years ago by Marcelo Forets

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.

comment:5 Changed 6 years ago by Matthias Köppe

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 Matthias Köppe

Branch: u/mkoeppe/setting_up_a_polyhedron_from_both_vrep_and_hrep

comment:7 Changed 4 years ago by Matthias Köppe

Authors: Matthias Koeppe
Cc: Travis Scrimshaw added
Commit: 6d91f255cacaf7fb89b3a8ad1ebcc470e7ef7437
Description: modified (diff)
Milestone: sage-8.0sage-8.4
Status: newneeds_review
Summary: Setting up a Polyhedron from both Vrep and HrepSetting up a Polyhedron from both Vrep and Hrep - for backend='field'

New commits:

cc73721Polyhedron_field._init_{H,V}representation_backend: Refactor through new methods _init_{H,V}representation
7a0438ePolyhedra_base._element_constructor: Refactor through new method _element_constructor_polyhedron
d6e0d68Polyhedra_field._element_constructor: Implement a version using both representations
6d91f25Polyhedron_field.__init__: New, handle Vrep+Hrep case

comment:8 Changed 4 years ago by Travis Scrimshaw

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 git

Commit: 6d91f255cacaf7fb89b3a8ad1ebcc470e7ef7437e34d84523dbb0602c1ca73d6ea3a59bb79f66425

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

e34d845Polyhedron_field.__init__: Reword error message, add docstring

comment:10 Changed 4 years ago by Matthias Köppe

(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.)

Last edited 4 years ago by Matthias Köppe (previous) (diff)

comment:11 Changed 4 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Thanks.

comment:12 Changed 4 years ago by Matthias Köppe

Thank you for the review.

comment:13 Changed 4 years ago by Matthias Köppe

Description: modified (diff)

comment:14 Changed 4 years ago by Volker Braun

Branch: u/mkoeppe/setting_up_a_polyhedron_from_both_vrep_and_hrepe34d84523dbb0602c1ca73d6ea3a59bb79f66425
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.