# affine group element * a polytope raises KeyError

Reported by: Owned by: slabbe major sage-9.2 geometry gh-kliem Sébastien Labbé Jonathan Kliem N/A cd687bc cd687bc3c4c67472b5c039701055598dd316e815

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
```

### 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:

 ​cd687bc `30327: define the left action of a affine group element on a polyhedron`

### 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.