#18678: Implement convolution_product for HopfAlgebras
-------------------------------------+-------------------------------------
Reporter: alauve | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.8
Component: categories | Resolution:
Keywords: days65, | Merged in:
convolution product | Reviewers:
Authors: Aaron Lauve | Work issues:
Report Upstream: N/A | Commit:
Branch: | de4fa8761667d770a5153e272c0522c8367188ca
u/alauve/implement_convolution_product_for_hopfalgebras| Stopgaps:
Dependencies: #18350 |
-------------------------------------+-------------------------------------
Changes (by alauve):
* status: needs_work => needs_review
Comment:
Hi Travis, Comments below...
Replying to [comment:13 tscrim]:
> Replying to [comment:11 alauve]:
> > I have merged #18350 with this ticket.
>
> I set this as a dependency.
I'm sure that's the wrong thing to do, but perhaps it's also the best
thing to do, given the steps I already took (merging). In fact, there is
''no dependency'', and the first thing I did was undo all the changes JBP
made to `hopf_algebras.py`. I think '''not both''' tickets should be
completed. I'm happy to move all my edits to #18350 and delete the present
ticket if that makes more sense... though I don't know how to do that
either.
Alternative?: set #18350 as positive review, as is, then start looking at
this one? .... I'm really not sure what is the best; see next comment for
more.
> > * I have moved `.adams_operator()` to `bialgebras.py`, and overwrote
it using code from Amy Pang (''amypang''). Then in `hopf_algebras.py` I
overwrote the bialgebras version, allowing for negative integer powers.
(E.g., the (-2)nd convolution power of the identity is none other than the
2nd power of the antipode.)
>
> I would make these changes on #18350 directly (I'd recommend `git
cherry-pick` the commit with that change in #18350 if it's in an isolated
commit, otherwise you'll have to deal with the merge conflict).
It was not an isolated commit (I've learned my lesson, thanks!).
Alternative idea, implemented in present ticket: I have deleted
`.adams_operator()` from `hopf_algebras.py` and from
`hopf_algebras_with_basis.py` and instead added an attribute check,
`hasattr(self,'antipode')` within `bialgebras.py` to allow for negative
convolution powers of the identity.
> > * In fact, while adams operators naturally belong in `bialgebras.py`,
the present code actually belongs in `bialgebras_with_basis.py`---as it
uses `.module_morphism()` and `.apply_multilinear_morphism()`---but this
would require more rewriting than I feel qualified to handle.
>
> Then I would move the method into `BialgebrasWithBasis` and put an
`@abstract_method(optional=True)` on an empty `adams_operators` in
`Bialgebras` (on #18350).
I don't know how to do the former (the move), as
`bialgebras_with_basis.py` just contains a '''def''' not a '''class'''.
Maybe there is a monkey-patching solution, overwriting whatever
ParentMethods and ElementMethods classes that get created by the
'''def''', but I'm comfortable trying neither this solution nor
overhauling the whole file (i.e., to make it look more like
`hopf_algebras_with_basis.py`).
Is there a better solution than the latter (abstract_method)? It's not
really ''optional''... more like ''not presently code-able''. Perhaps a
better solution is to keep things in `bialgebras.py`, perform an attribute
check, `self in ModulesWithBasis` and add "..TODO:: remove dependency on
bases" to the docstring? Anyhow, this is what I'm doing in latest commit.
> > * '''Easy fix?''' When poking around for an algebra without basis---on
which to test a preliminary version of my code---I noticed that Sage
doesn't know that `QQ[x]` is a module over `QQ` (and hence, one cannot
build ``QQ[x].tensor(QQ[x])`. Crazy.
>
> Sage is full of fun oddities like that. Personally I'm not opposed to
changing the category to `Algebras(QQ).WithBasis()`, but even with that,
I'd think there's still more work to do to get `QQ[x].tensor(QQ[x])` to
work...
I'm going to fiddle with this. If that's all it takes, I'll start a new
ticket and it should be completed easily enough.
> > * '''Easy fix?''' Similarly, even though `B = FreeAlgebra(QQ,a,b)` is
robust enough that `B.tensor(B)` doesn't throw errors, quotients are out-
of-bounds again. Putting `C = B.quotient_ring((a*b-b^2,))`, I get an
AttributeError when asking for `C.tensor(C)`.
>
> What is `a` and `b`? I think there is an abuse going on, but as of right
now I cannot even construct `B`.
Sorry. the code I ran was:
{{{
sage: B = FreeAlgebra(QQ,['a','b'])
sage: a,b = B.gens()
sage: B.tensor(B)
sage: C = B.quotient_ring((a*b-b^2,))
sage: C.tensor(C)
}}}
> > * I would like to add some morphism functionality at the parent level
before setting ticket to "needs_review": given linear morphisms R,S,T for
a bialgebra B, create their convolution product, a new morphism, via `RST
= B.convolution_product(R,S,T)`. However, it seems ticket #15832 will have
a lot of overlap with such code, so I'll hold off on implementing it
unless somebody suggests otherwise.
>
> I would work on #15832 and either create a follow-up with the additional
code or just add that code directly to #15832.
Found an alternative solution in present commit. If ever #15832 gets
adopted, the code here can be shortened by a few lines at most.
Note 1: But see comments in
`sage.categories.bialgebras.ParentMethods.convolution_product` regarding
speed.
Note 2: Also, I do not know how to keep `.convolution_product()` from
showing up in the list of methods available to, e.g.,
`sym=SymmetricFunctions(QQ)`. Any ideas on how to remove this?
(At present, the code assumes ''self'' is something more like
`SymmetricFunctions(QQ).m()` If the check wasn't there, Sage would throw
an error, because sym.tensor(sym) doesn't work.)...
{{{
sage: sym = SymmetricFunctions(QQ); m = sym.m()
sage: Id3 = m.convolution_product((lambda x: x,)*3)
sage: Id3(m[1]) == 3*m[1]
True
sage: sym.con <TAB>
sym.construction sym.convert_map_from sym.convolution_product
sage: sym.convolution_product((lambda x: x,)*3)
AttributeError: `self` (Symmetric Functions over Rational Field) must
belong to ModulesWithBasis. Try defining convolution product on a basis of
`self` instead.
}}}
> > * If anybody can explain why iterated coproduct followed by iterated
product is slower than Amy Pang's code, I'd love to hear it.
>
> I would add an `AUTHORS:` block and give Amy the credit for her code. I
have no idea at this point why this is. Try running `%prun the_command` to
get timing information and look through that data for hints. Also what
exactly are you testing this with? What is your timings (in particular,
the approximate slowdown factor)?
I have included a second ParentMethods command,
`_convolution_product_from_elements()` for others to investigate. I have
looked at %prun using `SymmetricFunctions(QQ).m()` and
`SymmetricGroupAlgebra(QQ,6)`, which have radically different Hopf
structure (and number of terms in product/coproduct). In both cases,
`_convolution_product_from_elements()` (based on Amy's code) destroys
`convolution_product()` (based on my code and Jean-Baptiste's code). I
can't glean much, other than that total number of operations are vastly
different.
{{{
sage: Id = lambda x: x
sage: m = SymmetricFunctions(QQ).m();
sage: mx = m[5,4,3,2,1]
sage: T1 = m.convolution_product((Id,)*4)
sage: timeit('T1(mx)',number=2,repeat=1)
2 loops, best of 1: 32 s per loop
sage: T2 = m._convolution_product_from_elements((Id,)*4)
sage: timeit('T2(mx)',number=2,repeat=1)
2 loops, best of 1: 32.3 s per loop
sage: mx = m[5,4,3,2,1]
sage: T1 = m.convolution_product((Id,)*7)
sage: timeit('T1(mx)',number=2,repeat=1)
2 loops, best of 1: 169 s per loop
sage: T2 = m._convolution_product_from_elements((Id,)*7)
sage: timeit('T2(mx)',number=2,repeat=1)
2 loops, best of 1: 80.3 s per loop
sage: qs = SymmetricGroupAlgebra(QQ,7); qsx = qs.an_element()^2; qsx
14*[1, 2, 3, 4, 5, 6, 7] + 4*[1, 2, 3, 4, 5, 7, 6] + 6*[1, 2, 3, 4, 6, 5,
7] + 6*[1, 2, 3, 4, 6, 7, 5] + 6*[1, 2, 3, 4, 7, 5, 6] + 2*[6, 1, 2, 3, 4,
5, 7] + [6, 7, 1, 2, 3, 4, 5] + 2*[7, 1, 2, 3, 4, 5, 6] + 5*[7, 1, 2, 3,
4, 6, 5] + 3*[7, 1, 2, 3, 5, 4, 6]
sage: T1 = qs.convolution_product(Id,Id,Id)
sage: timeit('T1(qsx)')
125 loops, best of 3: 3.98 ms per loop
sage: T2 = qs._convolution_product_from_elements(Id,Id,Id)
sage: timeit('T2(qsx)')
125 loops, best of 3: 3.4 ms per loop
sage: T1 = qs.convolution_product((Id,)*7)
sage: timeit('T1(qsx)')
25 loops, best of 3: 10.6 ms per loop
sage: T2 = qs._convolution_product_from_elements((Id,)*7)
sage: timeit('T2(qsx)')
25 loops, best of 3: 8.25 ms per loop
}}}
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=de4fa8761667d770a5153e272c0522c8367188ca
de4fa87]||{{{In ParentMethods of bialgebras.py, added
._convolution_product_from_element() for testing purposes.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/18678#comment:16>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
