#10052: Improve the implementation of the Steenrod algebra
-----------------------------------------------------------------------+----
Reporter: jhpalmieri |
Owner: AlexGhitza
Type: enhancement |
Status: needs_work
Priority: major |
Milestone: sage-4.6.1
Component: algebra |
Keywords: steenrod, notebook
Author: John Palmieri |
Upstream: N/A
Reviewer: |
Merged:
Work_issues: minor docstring issues, problems with sub-Hopf algebras |
-----------------------------------------------------------------------+----
Old description:
> The attached patch does several things:
>
> - it moves the Steenrod algebra code to a subdirectory of algebras. For
> one thing, there are already 4 files, and for another, I hope that more
> will be added: several people are working on related projects.
>
> - it reimplements the Steenrod algebra using `CombinatorialFreeModule`,
> which provides a number of conveniences: scalar multiplication is already
> defined, as are tensor products, etc. Then for example the antipode or
> the coproduct can be defined just on basis elements, and the linear
> extension to all elements is handled automatically.
>
> - it implements another way of computing products, using admissible
> sequences and the Adem relations. This provides a good way of checking
> for bugs: with two completely different algorithms for computing
> products, one can compute the same product two ways and compare answers.
>
> - it implements sub-Hopf algebras of the Steenrod algebra. These were
> classified 35 years ago, and for some applications people want to use
> sub-Hopf algebras rather than the whole thing.
>
> - the `TestSuite` has been improved: all components now pass, whereas
> before, we had some failures. From the ''old'' steenrod_algebra.py:
> {{{
> sage: TestSuite(A).run() # todo: fix category inheritance for
> elements of A
> Failure in _test_category:
> ...
> ------------------------------------------------------------
> The following tests failed: _test_category
> Failure in _test_elements
> The following tests failed: _test_elements
> }}}
> From the new one:
> {{{
> sage: TestSuite(SteenrodAlgebra()).run()
> sage: TestSuite(SteenrodAlgebra(profile=[4,3,2,2,1])).run()
> sage: TestSuite(SteenrodAlgebra(basis='adem')).run()
> sage: TestSuite(SteenrodAlgebra(basis='wall')).run()
> sage: TestSuite(SteenrodAlgebra(basis='arnonc')).run() # long
> time
> sage: TestSuite(SteenrodAlgebra(basis='woody')).run() # long
> time
> sage: A3 = SteenrodAlgebra(3)
> sage: A3.category()
> Category of graded hopf algebras with basis over Finite Field
> of size 3
> sage: TestSuite(A3).run()
> sage: TestSuite(SteenrodAlgebra(basis='adem', p=3)).run()
> sage: TestSuite(SteenrodAlgebra(basis='pst_llex', p=7)).run()
> # long time
> sage: TestSuite(SteenrodAlgebra(basis='comm_deg', p=5)).run()
> # long time
> }}}
> Not only are there no failures, but there are many more executions of
> the suite. This yields some repetition, but the method {{{an_element}}}
> varies depending on the values of {{{basis}}} and {{{p}}}, so there are
> also new tests run with each execution.
>
> Unfortunately, since the patch moves files around, it is large. It also
> trivially affects a few doctests in sageinspect, which means that it
> requires a patch to sagenb.
>
> This patch depends on #9370.
New description:
The attached patch does several things:
- it moves the Steenrod algebra code to a subdirectory of algebras. For
one thing, there are already 4 files, and for another, I hope that more
will be added: several people are working on related projects.
- it reimplements the Steenrod algebra using `CombinatorialFreeModule`,
which provides a number of conveniences: scalar multiplication is already
defined, as are tensor products, etc. Then for example the antipode or
the coproduct can be defined just on basis elements, and the linear
extension to all elements is handled automatically.
- it implements another way of computing products, using admissible
sequences and the Adem relations. This provides a good way of checking
for bugs: with two completely different algorithms for computing products,
one can compute the same product two ways and compare answers.
- it implements sub-Hopf algebras of the Steenrod algebra. These were
classified 35 years ago, and for some applications people want to use sub-
Hopf algebras rather than the whole thing.
- the `TestSuite` has been improved: all components now pass, whereas
before, we had some failures. From the ''old'' steenrod_algebra.py:
{{{
sage: TestSuite(A).run() # todo: fix category inheritance for
elements of A
Failure in _test_category:
...
------------------------------------------------------------
The following tests failed: _test_category
Failure in _test_elements
The following tests failed: _test_elements
}}}
From the new one:
{{{
sage: TestSuite(SteenrodAlgebra()).run()
sage: TestSuite(SteenrodAlgebra(profile=[4,3,2,2,1])).run()
sage: TestSuite(SteenrodAlgebra(basis='adem')).run()
sage: TestSuite(SteenrodAlgebra(basis='wall')).run()
sage: TestSuite(SteenrodAlgebra(basis='arnonc')).run() # long
time
sage: TestSuite(SteenrodAlgebra(basis='woody')).run() # long
time
sage: A3 = SteenrodAlgebra(3)
sage: A3.category()
Category of graded hopf algebras with basis over Finite Field
of size 3
sage: TestSuite(A3).run()
sage: TestSuite(SteenrodAlgebra(basis='adem', p=3)).run()
sage: TestSuite(SteenrodAlgebra(basis='pst_llex', p=7)).run()
# long time
sage: TestSuite(SteenrodAlgebra(basis='comm_deg', p=5)).run()
# long time
}}}
Not only are there no failures, but there are many more executions of the
suite. This yields some repetition, but the method {{{an_element}}}
varies depending on the values of {{{basis}}} and {{{p}}}, so there are
also new tests run with each execution.
Unfortunately, since the patch moves files around, it is large. It also
trivially affects a few doctests in sageinspect, which means that it
requires a patch to sagenb.
== Apply ==
1. Patch from #9370.
1. [attachment:trac_10052-steenrod.v3.patch].
--
Comment(by niles):
Replying to [comment:9 jhpalmieri]:
> Replying to [comment:8 niles]:
>
> Thanks a lot for all the work and careful comments. Among other things,
you've found some bugs in the code, which I think I've fixed. I'm
attaching a new patch, but I'm leaving it as "needs work" while I keep
looking at it to see if I can see other issues which need fixing.
Glad to help; I'll keep looking too. For now, some continued discussion
of printing and `.inject_variables()` . . .
> > * Two minor doctest failures
> I don't see these, on either sage.math or on OS X. What platform are
you using?
I'm using OS X, but Sage 4.5.2 for the first round of reviewing -- maybe
recent changes have fixed these problems.
> > * problems with coercion:
>
> I don't know how to fix this: it has to do with the implementation (or
lack thereof) of tensor products. I don't think it's particular to the
Steenrod algebra, so I'd like to have it dealt with on another ticket.
>
That sounds reasonable -- I'll try to work out the issue and put up a
ticket (unless you already know what the problem is).
> > * printing of elements: to be consistent with the rest of sage,
perhaps multiplication should print as `*`:
>
> I understand what you're saying, but I think that printing this way is
ugly. (This was one of the reasons for #9370.) If you really want, I can
change it, but I'd rather not.
Well, I'm not sure if this is a decision that should depend solely on my
opinion or yours; my thinking is that we should opt for consistency over
aesthetics unless there is a really good reason not to. Every other ring
in Sage prints multiplication as `*` -- do you have a good reason to
reverse that convention for the Steenrod algebra? (As you point out, this
is related to the question of whether or not #9370 is a good idea --
something I'm not sure of yet.) In particular, printing `*` is consistent
with the way Sage requires input to be typed (although note my further
comments on that topic below).
>
> > * it's too bad that elements do not print in a way that can be typed
directly into Sage (I think I read somewhere that this should be done
whenever possible).
After some looking, I think what I was remembering is this section of the
[http://www.sagemath.org/doc/tutorial/interactive_shell.html#saving-and-
loading-individual-objects interactive shell tutorial], which mentions
this idea as a possible way for printing objects, but one which Sage does
not enforce -- rather it suggests using un/pickling to store and retrieve
objects. Nevertheless, I think printing as closely as possible to valid
input is useful, especially for new users.
> Can `inject_variables` be used to define functions, not just variables?
I'll think about it, but I may want to defer it to a later ticket.
Fair enough; something like this does work for
[http://www.sagemath.org/doc/reference/sage/rings/polynomial/infinite_polynomial_element.html
infinite polynomial rings]:
{{{
sage: R = InfinitePolynomialRing(ZZ,'t')
sage: R
Infinite polynomial ring in t over Integer Ring
sage: R.inject_variables()
Defining t
sage: R.gens()
(t_*,)
sage: t[2]
t_2
sage: t[3]
t_3
sage: t[2]*t[3] - 4*t[11] + 8
-4*t_11 + t_3*t_2 + 8
sage: t[2]*t[3] - 4*t[11] + 8 in R
True
}}}
I think the way this is implemented is by defining a `__getitem__` method
for the generator, but the same should work by defining a `__call__`
method. (And I did notice, by the way, that the objects don't print in
the same way that they have to be input.) For infinite polynomial rings,
`.inject_variables()` is inherited from
`sage.structure.category_object.CategoryObject`:
{{{
def inject_variables(self, scope=None, verbose=True):
"""
Inject the generators of self with their names into the
namespace of the Python code from which this function is
called. Thus, e.g., if the generators of self are labeled
'a', 'b', and 'c', then after calling this method the
variables a, b, and c in the current scope will be set
equal to the generators of self.
NOTE: If Foo is a constructor for a Sage object with generators,
and
Foo is defined in Cython, then it would typically call
``inject_variables()`` on the object it creates. E.g.,
``PolynomialRing(QQ, 'y')`` does this so that the variable y is
the
generator of the polynomial ring.
"""
vs = self.variable_names()
gs = self.gens()
if scope is None:
scope = globals()
if verbose:
print "Defining %s"%(', '.join(vs))
for v, g in zip(vs, gs):
scope[v] = g
}}}
So if you want to use it, you would have to re-think what is returned by
`.gens()`, especially in the case of finitely-generated sub algebras. Of
course you could make a new definition of `.inject_variables()`, but it's
not clear this is a good idea either . . . I think this is worth a little
more thought, but shouldn't derail the rest of this ticket.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10052#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
