How is matrix action on vectors implemented?
Simon King
We have
sage: v = vector(ZZ,[1,2])
sage: M = matrix(ZZ,2,2,[1,2,3,4])
sage: cm = sage.structure.element.get_coercion_model()
sage: cm.explain(v.parent(),M.parent(),operator.mul)
Action discovered.
Right action by Full MatrixSpace of 2 by 2 dense matrices over
Integer Ring on Ambient free module of rank 2 over the principal ideal
domain Integer Ring
Result lives in Ambient free module of rank 2 over the principal ideal
domain Integer Ring
Ambient free module of rank 2 over the principal ideal domain Integer
Ring
But how does it work? I tried to search v.__mul__, v._acted_upon,
M._act_on, but didn't find it.
Cheers,
Simon
Robert Bradshaw
sage: M = matrix(ZZ, 2, 2)
sage: space = M.parent(); space
Full MatrixSpace of 2 by 2 dense matrices over Integer Ring
sage: space.get_act
space.get_action space.get_action_c space.get_action_impl
sage: space.get_action??
If get_action (and discover_action) are not overridden, the default is
to look for element._act_on, etc.
- Robert
Simon King
On 27 Dez., 22:26, Robert Bradshaw <rober...@math.washington.edu>
wrote:
> sage: space = M.parent(); space
> Full MatrixSpace of 2 by 2 dense matrices over Integer Ring
> sage: space.get_act
> space.get_action space.get_action_c space.get_action_impl
> sage: space.get_action??
>
> If get_action (and discover_action) are not overridden, the default is
> to look for element._act_on, etc.
I ask since space.get_action is inherited from
sage.structure.parent.Parent, where it says:
"To provide additional actions, override :meth:`_get_action_`."
However, space._get_action_ is not overridden but inherited from
sage.structure.parent_old.Parent, and since space._element_constructor
is None, the call is forwarded to space._get_action_c, which again is
inherited from sage.structure.parent_old.Parent.
Since space has a __dict__, eventually the action is obtained from
space.get_action_impl, which has no documentation. Confusing, and the
call forwarding is probably time consuming.
So, what should one do in the new Parent/coercion/category framework?
I guess that one has to override
sage.structure.parent.Parent._get_action_, correct? But how does one
define an action? I guess that one is supposed to use
sage.categories.action, but so far it has no example at all.
sage.categories.action.Action.__init__ tells that an action of G on S
is a functor from the category Groupoid(G) to S.category(), and the
documentation states "A group action $G \times S \rightarrow S$ is a
functor from $G$ to Sets."
That is rather obscure to me. Moreover,
sage.categories.action.Action.__call__ overrides the call method of
sage.categories.functor.Functor.__call__. So, I don't see a proper
relation between action and functor.
Isn't a group action A:GxS->S simply a homomorphism from G to Aut(S)?
How are these two definitions related? And is Aut(S) implemented in
Sage? At least it isn't under that name. Sometimes Aut(S) is called
Sym(S), but SymmetricGroup won't work in this context.
But apart from _get_action_: Isn't it possible to implement an action
by providing _r_action/_l_action or acts_upon/acted_upon? Which of the
many ways is preferred?
Cconclusion: For the moment, beyond acts_upon/acted_upon, I wouldn't
even know what to do in order to implement a simple action of, say,
Sym(n) on QQ[x_1,...,x_n] by variable permutation.
Cheers,
Simon
Robert Bradshaw
> Hi Robert!
>
> On 27 Dez., 22:26, Robert Bradshaw <rober...@math.washington.edu>
> wrote:
>> sage: M = matrix(ZZ, 2, 2)
>> sage: space = M.parent(); space
>> Full MatrixSpace of 2 by 2 dense matrices over Integer Ring
>> sage: space.get_act
>> space.get_action space.get_action_c space.get_action_impl
>> sage: space.get_action??
>>
>> If get_action (and discover_action) are not overridden, the default is
>> to look for element._act_on, etc.
>
> Is this how it does work or how it should work?
>
> I ask since space.get_action is inherited from
> sage.structure.parent.Parent, where it says:
> "To provide additional actions, override :meth:`_get_action_`."
>
> However, space._get_action_ is not overridden but inherited from
> sage.structure.parent_old.Parent, and since space._element_constructor
> is None, the call is forwarded to space._get_action_c, which again is
> inherited from sage.structure.parent_old.Parent.
>
> Since space has a __dict__, eventually the action is obtained from
> space.get_action_impl, which has no documentation. Confusing, and the
> call forwarding is probably time consuming.
That's because much of this pre-dates cpdef and is doing extra hoops
to use the old framework within the new framework. You're working on
moving modules over to the new coercion framework, right? This should
greatly simplify the call flow (I think we got rid of all _c and
_impl), and is long overdue Please feel free to ask if you have any
more questions--and I'm happy to contribute code too (just want to
avoid duplication of effort).
> So, what should one do in the new Parent/coercion/category framework?
> I guess that one has to override
> sage.structure.parent.Parent._get_action_, correct?
Yes.
> But how does one
> define an action? I guess that one is supposed to use
> sage.categories.action, but so far it has no example at all.
http://hg.sagemath.org/sage-main/file/120c07be6358/sage/matrix/action.pyx#l1
is the most comprehensive example to date.
> sage.categories.action.Action.__init__ tells that an action of G on S
> is a functor from the category Groupoid(G) to S.category(), and the
> documentation states "A group action $G \times S \rightarrow S$ is a
> functor from $G$ to Sets."
>
> That is rather obscure to me. Moreover,
> sage.categories.action.Action.__call__ overrides the call method of
> sage.categories.functor.Functor.__call__. So, I don't see a proper
> relation between action and functor.
>
> Isn't a group action A:GxS->S simply a homomorphism from G to Aut(S)?
It's a bit more generic than that, as we let Q act on Z[x] (with the
codomain being Q[x]).
> How are these two definitions related?
Consider the category with a single object whose morphisms are the
element of G. Then the functor send the elements of G to morphisms in
Sets.
> And is Aut(S) implemented in Sage?
Not in a useful way (that I know of), and even if it was there's no
good way to generically represent its elements.
> At least it isn't under that name. Sometimes Aut(S) is called
> Sym(S), but SymmetricGroup won't work in this context.
>
> But apart from _get_action_: Isn't it possible to implement an action
> by providing _r_action/_l_action or acts_upon/acted_upon? Which of the
> many ways is preferred?
For module actions, implement _rmul_ and _lmul_. This has the
advantage of inserting a couple of nice coercions (the group element
is always coerced into the basering). Otherwise, implement acts_upon
or acted_upon is preferred, whichever makes the most sense.
_r_action/_l_action is primarily for things which don't fit into the
framework (e.g. permutations acting on lists, or ints.)
> Cconclusion: For the moment, beyond acts_upon/acted_upon, I wouldn't
> even know what to do in order to implement a simple action of, say,
> Sym(n) on QQ[x_1,...,x_n] by variable permutation.
acts_upon is probably the right thing do do here. For something more
complicated, see
http://hg.sagemath.org/sage-main/file/120c07be6358/sage/matrix/matrix_space.py#l474
.
- Robert
Simon King
On 28 Dez., 01:27, Robert Bradshaw <rober...@math.washington.edu>
wrote:
> ... You're working on
> > But how does one
> > define an action? I guess that one is supposed to use
> > sage.categories.action, but so far it has no example at all.
>
matrix action works. However, I couldn't see how it relates with
functors, since it seems to me that it overrides all "typical" methods
of functors.
> > How are these two definitions related?
>
> Consider the category with a single object whose morphisms are the
> element of G. Then the functor send the elements of G to morphisms in
> Sets.
documentation.
sage.categories.action.Action.__init__ is
{{{
def __init__(self, G, S, bint is_left = 1, op=None):
from groupoid import Groupoid
Functor.__init__(self, Groupoid(G), S.category())
self.G = G
self.S = S
self._is_left = is_left
self.op = op
}}}
and sage.categories.action.__doc__ states "A group action G x S
rightarrow S is a functor from G to Sets."
According to your post, it should be "A group action G x S rightarrow
S is a functor from G (considered as a category) to the category of
Morphisms of Sets", and in the code it should be
Functor.__init__(self, Groupoid(G), S.category().hom_category()).
Moreover, sage.matrix.action.MatrixMatrixAction is implemented by a
_call_ method that has the signature
cpdef Element _call_(self, g, s)
Hence, essentially it is a map (not a functor) from GxS to S -- so,
the implementation uses the category-free definition of an action, but
pretends to be categorical.
One crucial question is, IMO:
Would it really be wise to use a categorical approach towards actions?
Using the categorical definition would mean: To any given element g of
G, create a morphism from S to S (very slow!), and apply it to a given
element s of S. I guess caching the morphism from S to S would not
really be a solution. So, the current approach to think of an action
as a map from GxS to S probably yields a better implementation (speed-
wise).
But then, the question is what one should do with
sage.categories.action? Should it be overhauled so that it really
matches the categorical definition, just for completeness, even though
it would not be used in Sage?
Should there also be an "official" new framework for the non-
categorical version of an action, say, in sage.structure.action? Then,
actions that currently tacitly use the non-categorical definition
(like MatrixMatrixAction) could finally be "officially non-
categorical"?
Cheers,
Simon
Simon King
> Moreover, sage.matrix.action.MatrixMatrixAction is implemented by a
> _call_ method that has the signature
> cpdef Element _call_(self, g, s)
> Hence, essentially it is a map (not a functor) from GxS to S
doesn't change the fact that it makes no use of the functor framework.
Simon King
I guess further discussion should be moved to sage-algebra. See
http://groups.google.com/group/sage-algebra/browse_thread/thread/1787794a7a42cfb5
Cheers,
Simon
Robert Bradshaw
> Hi Robert,
>
> On 28 Dez., 01:27, Robert Bradshaw <rober...@math.washington.edu>
> wrote:
>> ... You're working on
>> moving modules over to the new coercion framework, right?
>
> Yes.
>
>> > But how does one
>> > define an action? I guess that one is supposed to use
>> > sage.categories.action, but so far it has no example at all.
>>
>> http://hg.sagemath.org/sage-main/file/120c07be6358/sage/matrix/action...
>> is the most comprehensive example to date.
>
> Yes, I had looked at that example when I tried to understand how
> matrix action works. However, I couldn't see how it relates with
> functors, since it seems to me that it overrides all "typical" methods
> of functors.
>
>> > How are these two definitions related?
>>
>> Consider the category with a single object whose morphisms are the
>> element of G. Then the functor send the elements of G to morphisms in
>> Sets.
>
> That makes sense, but it does neither match the code nor the
> documentation.
I agree 100%. This is a case of someone (likely me) trying to map a
single mathematical view of an object onto an implementation. Even if
there is an "is a" relationship, it would probably make more sense for
Action to not inherit from Functor, as they behave and are used
completely differently.
> sage.categories.action.Action.__init__ is
> {{{
> def __init__(self, G, S, bint is_left = 1, op=None):
> from groupoid import Groupoid
> Functor.__init__(self, Groupoid(G), S.category())
> self.G = G
> self.S = S
> self._is_left = is_left
> self.op = op
> }}}
> and sage.categories.action.__doc__ states "A group action G x S
> rightarrow S is a functor from G to Sets."
>
> According to your post, it should be "A group action G x S rightarrow
> S is a functor from G (considered as a category) to the category of
> Morphisms of Sets", and in the code it should be
> Functor.__init__(self, Groupoid(G), S.category().hom_category()).
Not quite. It is G considered as a category where the elements of G
are the morphisms and there only one object, so it is actually a
functor to the categories of sets. But, as I've stated above, this is
not the most useful perspective of an action (in our context at
least).
> Moreover, sage.matrix.action.MatrixMatrixAction is implemented by a
> _call_ method that has the signature
> cpdef Element _call_(self, g, s)
> Hence, essentially it is a map (not a functor) from GxS to S -- so,
> the implementation uses the category-free definition of an action, but
> pretends to be categorical.
>
> One crucial question is, IMO:
> Would it really be wise to use a categorical approach towards actions?
I don't think so. Especially now that the category framework allows
attaching abstract mathematical structure to objects independent of
their inheritance and implementation.
> Using the categorical definition would mean: To any given element g of
> G, create a morphism from S to S (very slow!), and apply it to a given
> element s of S. I guess caching the morphism from S to S would not
> really be a solution. So, the current approach to think of an action
> as a map from GxS to S probably yields a better implementation (speed-
> wise).
It's often useful to be able to obtain the morphism corresponding to
any element (there is currently such a method on actions), but as
reflected in the current state of things and your comments this does
not yield a good implementation.
> But then, the question is what one should do with
> sage.categories.action? Should it be overhauled so that it really
> matches the categorical definition, just for completeness, even though
> it would not be used in Sage?
>
> Should there also be an "official" new framework for the non-
> categorical version of an action, say, in sage.structure.action? Then,
> actions that currently tacitly use the non-categorical definition
> (like MatrixMatrixAction) could finally be "officially non-
> categorical"?
Unless I'm mistaken, nearly every action that's used is in the context
of the coercion framework, which, though I want it to be
mathematically sound, I consider to be as much of a user interface
component as a mathematical one.
In fact, I just did a search through the sage sources and it looks
like there aren't any Actions other than the coercion one, so we could
probably just cut out the (weak) categorical ties.
- Robert
Simon King
On 28 Dez., 23:41, Robert Bradshaw <rober...@math.washington.edu>
wrote:
> > S is a functor from G (considered as a category) to the category of
> > Morphisms of Sets", and in the code it should be
> > Functor.__init__(self, Groupoid(G), S.category().hom_category()).
>
> Not quite. It is G considered as a category where the elements of G
> are the morphisms and there only one object, so it is actually a
> functor to the categories of sets.
it is not Groupoid(G) (as one might expect from the code snippet
above):
sage: G = SymmetricGroup(5)
sage: C = Groupoid(G)
sage: G.random_element() in C.hom_category()
False
Shouldn't the last line return "True"?
I'd like to provide both the categorical approach towards actions and
the other approach: It would be up to the user what approach to use
for a new action, and there should be a way to consider any action
both as a functor and as a map, regardless how it was defined (see my
post on sage-algebra).
But before that is possible, it seems that one needs to provide a
proper HomCategory for groupoids with a __contains__ method that
relies on containment in the underlying set.
Cheers,
Simon
Robert Bradshaw
> Hi Robert,
>
> On 28 Dez., 23:41, Robert Bradshaw <rober...@math.washington.edu>
> wrote:
>> > According to your post, it should be "A group action G x S rightarrow
>> > S is a functor from G (considered as a category) to the category of
>> > Morphisms of Sets", and in the code it should be
>> > Functor.__init__(self, Groupoid(G), S.category().hom_category()).
>>
>> Not quite. It is G considered as a category where the elements of G
>> are the morphisms and there only one object, so it is actually a
>> functor to the categories of sets.
>
> I see. But is that category actually implemented in Sage? Apparently
> it is not Groupoid(G) (as one might expect from the code snippet
> above):
> sage: G = SymmetricGroup(5)
> sage: C = Groupoid(G)
> sage: G.random_element() in C.hom_category()
> False
>
> Shouldn't the last line return "True"?
Hmm... Groupoid is the wrong category here. Or, rather, the category
we want is a groupoid, but not this one.
> I'd like to provide both the categorical approach towards actions and
> the other approach: It would be up to the user what approach to use
> for a new action, and there should be a way to consider any action
> both as a functor and as a map, regardless how it was defined (see my
> post on sage-algebra).
I'd say it would make sense to implement Actions as a mapping G x S ->
S', which is essentially what the implementation is now. There should
be functions provided to view this as a map G -> Hom(S, S') and as a
functor, but the inheritance is certainly odd and wrong the way it is
now.
> But before that is possible, it seems that one needs to provide a
> proper HomCategory for groupoids with a __contains__ method that
> relies on containment in the underlying set.
Should containment be for morphisms, objects, or both?
- Robert
Simon King
On 29 Dez., 20:04, Robert Bradshaw <rober...@math.washington.edu>
wrote:
> On Tue, Dec 28, 2010 at 11:49 PM, Simon King <simon.k...@uni-jena.de> wrote:
> > ...
> > sage: C = Groupoid(G)
> > sage: G.random_element() in C.hom_category()
> > False
>
> > Shouldn't the last line return "True"?
>
> Hmm... Groupoid is the wrong category here. Or, rather, the category
> we want is a groupoid, but not this one.
http://groups.google.com/group/sage-algebra/browse_thread/thread/3e2ca2a8be1a3a23
(I think this discussion should be moved to sage-algebra):
If g is an element of G, then "g in C.hom_category()" should of
course return "False", since g is not a homset (but it is contained
in a homset).
Note that we currently have
sage: R.<x,y,z> = ZZ[]
sage: f = R.hom([x^2,y^2,z^2])
sage: C = R.category()
sage: f in C.hom_category()
True
which I think is a bug.
I think one *should* test the property of being a morphism by
"parent(g) in Groupoid(G).hom_category()" (which is not implemented
yet) resp. "parent(f) in C.hom_category()" (which works already).
> I'd say it would make sense to implement Actions as a mapping G x S ->
> S', which is essentially what the implementation is now. There should
> be functions provided to view this as a map G -> Hom(S, S') and as a
> functor, but the inheritance is certainly odd and wrong the way it is
> now.
> Should containment be for morphisms, objects, or both?
C.hom_category()".
Cheers,
Simon