#30327 closed defect (fixed)

affine group element * a polytope raises KeyError

Reported by: slabbe Owned by:
Priority: major Milestone: sage-9.2
Component: geometry Keywords:
Cc: gh-kliem Merged in:
Authors: Sébastien Labbé Reviewers: Jonathan Kliem
Report Upstream: N/A Work issues:
Branch: cd687bc (Commits, GitHub, GitLab) Commit: cd687bc3c4c67472b5c039701055598dd316e815
Dependencies: Stopgaps:

Status badges

Description (last modified by slabbe)

This works:

sage: cube = polytopes.cube()
sage: M = random_matrix(QQ,3,3)
sage: v = vector(QQ,(1,2,3))
sage: M*cube
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 8 vertices
sage: M*cube + v
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 8 vertices

but

sage: cube = polytopes.cube()
sage: M = random_matrix(QQ,3,3)
sage: v = vector(QQ,(1,2,3))
sage: F = AffineGroup(3, QQ)
sage: f = F(M, v)
sage: f * cube

or

sage: f(cube)

both raises

Traceback (most recent call last):
/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10038)()
   1188         try:
-> 1189             action = self._action_maps.get(xp, yp, op)
   1190         except KeyError:

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/coerce_dict.pyx in sage.structure.coerce_dict.TripleDict.get (build/cythonized/sage/structure/coerce_dict.c:8025)()
   1327         if not valid(cursor.key_id1):
-> 1328             raise KeyError((k1, k2, k3))
   1329         value = <object>cursor.value

KeyError: (Affine Group of degree 3 over Integer Ring, Polyhedra in ZZ^3, <built-in function mul>)

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call last)
<ipython-input-21-ea5fb26d6780> in <module>()
----> 1 f * P

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__mul__ (build/cythonized/sage/structure/element.c:12139)()
   1513             return (<Element>left)._mul_(right)
   1514         if BOTH_ARE_ELEMENT(cl):
-> 1515             return coercion_model.bin_op(left, right, mul)
   1516 
   1517         cdef long value

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10088)()
   1189             action = self._action_maps.get(xp, yp, op)
   1190         except KeyError:
-> 1191             action = self.get_action(xp, yp, op, x, y)
   1192         if action is not None:
   1193             if (<Action>action)._is_left:

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.get_action (build/cythonized/sage/structure/coerce.c:16920)()
   1718         except KeyError:
   1719             pass
-> 1720         action = self.discover_action(R, S, op, r, s)
   1721         action = self.verify_action(action, R, S, op)
   1722         self._action_maps.set(R, S, op, action)

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.discover_action (build/cythonized/sage/structure/coerce.c:18356)()
   1849         """
   1850         if isinstance(R, Parent):
-> 1851             action = (<Parent>R).get_action(S, op, True, r, s)
   1852             if action is not None:
   1853                 return action

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.get_action (build/cythonized/sage/structure/parent.c:20150)()
   2475         action = self._get_action_(S, op, self_on_left)
   2476         if action is None:
-> 2477             action = self.discover_action(S, op, self_on_left, self_el, S_el)
   2478 
   2479         if action is not None:

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.discover_action (build/cythonized/sage/structure/parent.c:21136)()
   2554                 # detect actions defined by _rmul_, _lmul_, _act_on_, and _acted_upon_ methods
   2555                 from .coerce_actions import detect_element_action
-> 2556                 action = detect_element_action(self, S, self_on_left, self_el, S_el)
   2557                 if action is not None:
   2558                     return action

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.detect_element_action (build/cythonized/sage/structure/coerce_actions.c:5242)()
    221     # element x defining _act_on_
    222     try:
--> 223         if x._act_on_(y, X_on_left) is not None:
    224             return ActOnAction(X, Y, X_on_left, False)
    225     except CoercionException:

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element._act_on_ (build/cythonized/sage/structure/element.c:8681)()
    942         return self.subs(in_dict,**kwds)
    943 
--> 944     cpdef _act_on_(self, x, bint self_on_left):
    945         """
    946         Use this method to implement ``self`` acting on ``x``.

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/groups/affine_gps/group_element.py in _act_on_(self, x, self_on_left)
    380         """
    381         if self_on_left:
--> 382             return self(x)
    383 
    384     def inverse(self):

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/groups/affine_gps/group_element.py in __call__(self, v)
    358             image_coords = self._A * vector(ring, ring.gens()) + self._b
    359             return v(*image_coords)
--> 360         v = parent.vector_space()(v)
    361         return self._A*v + self._b
    362 

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9305)()
    898         if mor is not None:
    899             if no_extra_args:
--> 900                 return mor._call_(x)
    901             else:
    902                 return mor._call_with_args(x, args, kwds)

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4591)()
    159                 print(type(C), C)
    160                 print(type(C._element_constructor), C._element_constructor)
--> 161             raise
    162 
    163     cpdef Element _call_with_args(self, x, args=(), kwds={}):

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4483)()
    154         cdef Parent C = self._codomain
    155         try:
--> 156             return C._element_constructor(x)
    157         except Exception:
    158             if print_warnings:

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/modules/free_module.py in _element_constructor_(self, x, coerce, copy, check)
   1024         if check and self.coordinate_ring().is_exact():
   1025             if isinstance(self, FreeModule_ambient):
-> 1026                 return self.element_class(self, x, coerce, copy)
   1027             try:
   1028                 c = self.coordinates(x)

/home/slabbe/GitBox/sage/local/lib/python3.7/site-packages/sage/modules/vector_integer_dense.pyx in sage.modules.vector_integer_dense.Vector_integer_dense.__init__ (build/cythonized/sage/modules/vector_integer_dense.c:3569)()
    124             return
    125         if x != 0:
--> 126             raise TypeError("can't initialize vector from nonzero non-list")
    127 
    128     def __dealloc__(self):

TypeError: can't initialize vector from nonzero non-list

Change History (5)

comment:1 Changed 14 months ago by slabbe

  • Authors set to Sébastien Labbé
  • Branch set to u/slabbe/30327
  • Commit set to cd687bc3c4c67472b5c039701055598dd316e815
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

cd687bc30327: define the left action of a affine group element on a polyhedron

comment:2 Changed 14 months ago by mkoeppe

  • Cc gh-kliem added

comment:3 Changed 14 months ago by gh-kliem

+            return self._A*v + self._b

One quick comment about this line, because I want people that use this stuff to be aware of it:

You do it in the correct order (it is natural here). For a polyhedron P computing A*P + A*b might be much faster than A*(P+b), mostly because P+b might change the base ring already, which might make an_affine_basis hard to compute. Also P.an_affine_basis() might be known already. Lots of "mights", but I have seen dramatic speed penalties. See #29843 for details.

comment:4 Changed 14 months ago by gh-kliem

  • Reviewers set to Jonathan Kliem
  • Status changed from needs_review to positive_review

LGTM.

Last edited 14 months ago by gh-kliem (previous) (diff)

comment:5 Changed 13 months ago by vbraun

  • Branch changed from u/slabbe/30327 to cd687bc3c4c67472b5c039701055598dd316e815
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.