Opened 2 years ago

Closed 9 months ago

#22701 closed enhancement (fixed)

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

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-8.4
Component: geometry Keywords: polytope, geometry, days84
Cc: jipilab, mforets, moritz, novoselt, tscrim Merged in:
Authors: Matthias Koeppe Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: e34d845 (Commits) Commit: e34d84523dbb0602c1ca73d6ea3a59bb79f66425
Dependencies: Stopgaps:

Description (last modified by 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:

  • #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 2 years ago by mkoeppe

  • Description modified (diff)

comment:2 Changed 2 years ago by moritz

  • Cc moritz added

comment:3 Changed 2 years ago by novoselt

  • Cc novoselt added

comment:4 Changed 2 years ago by mforets

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 2 years ago by mkoeppe

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 9 months ago by mkoeppe

  • Branch set to u/mkoeppe/setting_up_a_polyhedron_from_both_vrep_and_hrep

comment:7 Changed 9 months ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Cc tscrim added
  • Commit set to 6d91f255cacaf7fb89b3a8ad1ebcc470e7ef7437
  • Description modified (diff)
  • Milestone changed from sage-8.0 to sage-8.4
  • Status changed from new to needs_review
  • Summary changed from Setting up a Polyhedron from both Vrep and Hrep to Setting 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 9 months ago by tscrim

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 9 months ago by git

  • Commit changed from 6d91f255cacaf7fb89b3a8ad1ebcc470e7ef7437 to e34d84523dbb0602c1ca73d6ea3a59bb79f66425

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

e34d845Polyhedron_field.__init__: Reword error message, add docstring

comment:10 Changed 9 months ago by mkoeppe

(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 9 months ago by mkoeppe (previous) (diff)

comment:11 Changed 9 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Thanks.

comment:12 Changed 9 months ago by mkoeppe

Thank you for the review.

comment:13 Changed 9 months ago by mkoeppe

  • Description modified (diff)

comment:14 Changed 9 months ago by vbraun

  • Branch changed from u/mkoeppe/setting_up_a_polyhedron_from_both_vrep_and_hrep to e34d84523dbb0602c1ca73d6ea3a59bb79f66425
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.