* author: => Darij Grinberg
* component: PLEASE CHANGE => combinatorics
* owner: tbd => sage-combinat
* keywords: => symmetric function, combinat, kronecker product
* type: PLEASE CHANGE => enhancement
Old description:
> Will supply description in half an hour.
New description:
Will supply description in half an hour.
"extend" == The current version only works when the ground ring is an
algebra over the rationals, whereas mathematically this is not necessary.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB
* cc: zabrocki, aschilling, tscrim (added)
* keywords: symmetric function, combinat, kronecker product => symmetric
function, combinat, kronecker product, days49
Old description:
> Will supply description in half an hour.
>
> "extend" == The current version only works when the ground ring is an
> algebra over the rationals, whereas mathematically this is not necessary.
New description:
Will supply description in half an hour.
"extend" == The current version only works when the ground ring is an
algebra over the rationals, whereas mathematically this is not necessary.
I'd love someone to check the hacks used in the current file (even if it's
far from complete -- it only attempts to implement the Kronecker product
over any base ring) and tell me which of them are bad before I spread them
into other functions.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:2>
* cc: nthiery (added)
Old description:
> Will supply description in half an hour.
>
> "extend" == The current version only works when the ground ring is an
> algebra over the rationals, whereas mathematically this is not necessary.
>
> I'd love someone to check the hacks used in the current file (even if
> it's far from complete -- it only attempts to implement the Kronecker
> product over any base ring) and tell me which of them are bad before I
> spread them into other functions.
New description:
Goals for this ticket:
- The current version of itensor (the Kronecker product on the ring of
symmetric function) only works when the ground ring is an algebra over the
rationals. This is not a mathematically reasonable restriction. Fix this.
- The Kronecker coproduct on the ring of symmetric function has to be
implemented. Implement it.
- The forgotten basis of Symm is defined by duality rather than by
explicit formulas. As a consequence, it cannot be computed when the ground
ring is not a field. This might be easily fixable or not depending on how
smart our dual basis methods are; either way, fix it.
- The Witt symmetric functions form another basis of Symm. Implement them.
The current file has the first goal achieved, but it uses some sly hacks.
Can anyone tell me which of them are bad before I spread them into other
functions (particularly for the second goal)?
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:3>
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:4>
Comment (by darij):
3 is done. Anyone has a better name than {{{degree_negation}}} for the
algebra automorphism of ``SymmetricFunctions`` which acts as 1 in even
degrees and 0 in odd ones?
The changes in the antipode method not only made it work over any rings,
but also sped it up on each basis except for the powersum one (and the
monomial one, but I improved that with a trivial fix):
Test suite:
{{{
def testall():
Sym = SymmetricFunctions(QQ)
print "m"
timeit("SymmetricFunctions(QQ).m()([4,3,2]).antipode()")
print "h"
timeit("SymmetricFunctions(QQ).h()([4,3,2]).antipode()")
print "e"
timeit("SymmetricFunctions(QQ).e()([4,3,2]).antipode()")
print "s"
timeit("SymmetricFunctions(QQ).s()([4,3,2]).antipode()")
print "p"
timeit("SymmetricFunctions(QQ).p()([4,3,2]).antipode()")
}}}
Results:
{{{
original version:
sage: testall()
m
125 loops, best of 3: 1.86 ms per loop
h
25 loops, best of 3: 10.8 ms per loop
e
25 loops, best of 3: 10.8 ms per loop
s
25 loops, best of 3: 30.6 ms per loop
p
625 loops, best of 3: 146 µs per loop
after change of generic antipode to go via omega rather than via coercion
to powersum basis:
sage: testall()
m
125 loops, best of 3: 2.16 ms per loop
h
125 loops, best of 3: 2.92 ms per loop
e
125 loops, best of 3: 2.92 ms per loop
s
625 loops, best of 3: 250 µs per loop
p
625 loops, best of 3: 148 µs per loop
after microoptimization in the antipode of powersum (replacing (-1)**blah
by case distinction):
sage: testall()
m
125 loops, best of 3: 1.79 ms per loop
h
125 loops, best of 3: 2.88 ms per loop
e
125 loops, best of 3: 2.95 ms per loop
s
625 loops, best of 3: 252 µs per loop
p
625 loops, best of 3: 113 µs per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:5>
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:6>
Comment (by darij):
New version up, with forgotten functions working over every base ring.
I've attached two files which show some timings for conversions from and
to f. The times over a base ring which is a QQ-algebra have become a tad
worse, although probably not significantly (what are our criteria for
that?). The times over a base ring which is a QQ-algebra differ
significantly from those over a base ring which is not, although not in a
sufficiently consistent way for me to prefer one method over the other.
In other news, this patch has profited much from input by Nicolas Thiery,
Mike Zabrocki, Florent Hivert and Simon King. Thank you!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:7>
Comment (by darij):
If anyone could comment on my {{{witt.py}}} file in [attachment:trac_14775
-symmetric_functions_extended-dg.patch], I'd be much indebted (while the
coercions seem to work, my understanding of OOP is still very fragmentary
and I wouldn't be surprised if some of what I've done is bad practice). I
am going to add more doctests, implement coercions/conversions to power
sums and elementary symmetrics. (And if I really have too much time on my
hand, I'll add Frobenius and Verschiebung maps.)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:8>
Comment (by darij):
While there are good formulas for the h, e, p bases in terms of the w
bases, as well as not-too-slow algorithms for the w basis in terms of the
h, e, p bases (basically by inverting the formulas just mentioned), I am
not sure which of them I should implement. Right now I have implemented
h-to-w and w-to-h, declaring them as coercions, and p-to-w. The h-to-w and
w-to-h coercions use a cache like the ones in {{{dual.py}}}. Now I need
guidance on the following:
1) Is it a good idea to also use cache for e-to-w and w-to-e? (The
downside is that there will be more caches in memory.) Same for p-to-w (my
current implementation is cacheless, thus not as fast as it could be) and
w-to-p.
2) If I implement these maps, should I register them as coersions? (This
would normally make sense, but I fear they could significantly slow down
coercions between standard classical bases because of the asinine way the
current system generates coercion paths.)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:9>
* cc: hivert, sage-combinat (added)
* status: new => needs_info
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:10>
Comment (by aschilling):
Hi Darij,
Could you run some benchmarks to check what happens when you implement and
register the above mentioned coercions?
Anne
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:11>
Comment (by nthiery):
Replying to [comment:9 darij]:
> 1) Is it a good idea to also use cache for e-to-w and w-to-e? (The
downside is that there will be more caches in memory.) Same for p-to-w (my
current implementation is cacheless, thus not as fast as it could be) and
w-to-p.
Only practice will tell, and you'll probably be the one putting this
most to practice; I'd say don't cache for now, and see later if
you need it.
And at some point in the future we would want a mechanism that would
allow the user to specify which caches he want to use for his own
preferred application.
> 2) If I implement these maps, should I register them as coersions?
> (This would normally make sense, but I fear they could significantly
> slow down coercions between standard classical bases because of the
> asinine way the current system generates coercion paths.)
Go ahead. For most classical basis, Symmetrica provides a direct
conversion, and when there is one the coercion system is not as stupid
as using his depth first search :-)
In any case, if something would need to be fixed, it's the coercion
system, not the usage of coercions as above.
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:12>
--
Comment (by darij):
Uploading a new version, mostly with docstring fixes. Thanks for your
replies, Anne and Nicolas; I'll work on this shortly (haven't returned to
the Witt symmetric functions yet).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:13>
* status: needs_info => needs_review
Old description:
> Goals for this ticket:
>
> 1. The current version of itensor (the Kronecker product on the ring of
> symmetric function) only works when the ground ring is an algebra over
> the rationals. This is not a mathematically reasonable restriction. Fix
> this.
>
> 2. The Kronecker coproduct on the ring of symmetric function has to be
> implemented. Implement it.
>
> 3. The antipode on the ring of symmetric functions uses coercion into the
> powersum basis. This means it, too, is not getting computed over
> arbitrary base rings. Fix this.
>
> 4. The forgotten basis of Symm is defined by duality rather than by
> explicit formulas. Our duality methods use the powersum basis, again
> leading to errors for ground rings not being QQ-algebras.
>
> 5. The Witt symmetric functions form another basis of Symm. Implement
> them.
>
> 6. Implement Frobenius and Verschiebung operations on Symm without
> recourse to plethysm.
>
> The current file has the first goal achieved, but it uses some sly hacks.
> Can anyone tell me which of them are bad before I spread them into other
> functions (particularly for the second goal)?
New description:
This ticket does the following:
1. The current version of itensor (the Kronecker product on the ring of
symmetric function) only works when the ground ring is an algebra over the
rationals. This is not a mathematically reasonable restriction. Fix this.
2. The Kronecker coproduct on the ring of symmetric function has to be
implemented. Implement it.
3. The antipode on the ring of symmetric functions uses coercion into the
powersum basis. This means it, too, is not getting computed over arbitrary
base rings. Fix this.
4. The forgotten basis of Symm is defined by duality rather than by
explicit formulas. Our duality methods use the powersum basis, again
leading to errors for ground rings not being QQ-algebras.
5. The Witt symmetric functions form another basis of Symm. Implement
them.
6. Implement Frobenius and Verschiebung operations on Symm without
recourse to plethysm.
* Apply: [attachment:trac_14775-symmetric_functions_extended-dg.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:14>
Comment (by darij):
Done!
@Anne: I've run some benchmarks (which show that caching the coercions to
all of the h, e and p bases is a lot better than caching only the one to
the h basis). But they don't mean very much since Sage, in the absence of
a direct coercion, looks for a compound coercion by depth-first search
(which can be, and is in my case, extremely slow). I was too lazy to
manually register 2-step coercions, so I went a different way and gave the
user the freedom to decide what coercions to cache.
In other news, this patch probably conflicts with every other patch that
edits symmetric functions -- sorry.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:15>
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:16>
Comment (by darij):
If you are wondering about the latest change: I removed an obsolete TODO
which was already done. Sorry for that being in the patch in the first
place.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:17>
Comment (by aschilling):
> @Anne: I've run some benchmarks (which show that caching the coercions
to all of the h, e and p bases is a lot better than caching only the one
to the h basis). But they don't mean very much since Sage, in the absence
of a direct coercion, looks for a compound coercion by depth-first search
(which can be, and is in my case, extremely slow). I was too lazy to
manually register 2-step coercions, so I went a different way and gave the
user the freedom to decide what coercions to cache.
Darij, could you post the results of your benchmarks?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:18>
* cc: mhansen (added)
Comment:
Here's one:
{{{
sage: Sym = SymmetricFunctions(QQ)
sage: Sym.inject_shorthands()
/home/darij/sage-5.11.beta3/local/lib/python2.7/site-
packages/sage/combinat/sf/sf.py:1174: RuntimeWarning: redefining global
value `e`
inject_variable(shorthand, getattr(self, shorthand)())
sage: w = Sym.w()
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 105 µs per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 103 µs per loop
sage: timeit("e(w[4,3,2,1])")
5 loops, best of 3: 75.5 ms per loop
sage: timeit("w(e[4,3,2,1])")
5 loops, best of 3: 3.26 ms per loop
sage: timeit("s(w[4,3,2,1])")
5 loops, best of 3: 67.6 ms per loop
sage: timeit("w(s[4,3,2,1])")
125 loops, best of 3: 1.73 ms per loop
sage: timeit("p(w[4,3,2,1])")
25 loops, best of 3: 8.5 ms per loop
sage: timeit("w(p[4,3,2,1])")
125 loops, best of 3: 1.88 ms per loop
sage:
sage: w = Sym.w(coerce_h=False, coerce_p=True)
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 45.4 µs per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 102 µs per loop
sage: timeit("e(w[4,3,2,1])")
5 loops, best of 3: 75.9 ms per loop
sage: timeit("w(e[4,3,2,1])")
5 loops, best of 3: 1.86 ms per loop
sage: timeit("s(w[4,3,2,1])")
5 loops, best of 3: 67.4 ms per loop
sage: timeit("w(s[4,3,2,1])")
5 loops, best of 3: 1.63 ms per loop
sage: timeit("p(w[4,3,2,1])")
625 loops, best of 3: 96.1 µs per loop
sage: timeit("w(p[4,3,2,1])")
625 loops, best of 3: 95.9 µs per loop
sage:
sage: w = Sym.w(coerce_h=False, coerce_e=True)
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 246 ms per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 1.51 ms per loop
sage: timeit("e(w[4,3,2,1])")
625 loops, best of 3: 88.5 µs per loop
sage: timeit("w(e[4,3,2,1])")
625 loops, best of 3: 87.3 µs per loop
sage: timeit("s(w[4,3,2,1])")
25 loops, best of 3: 9.33 ms per loop
sage: timeit("w(s[4,3,2,1])")
625 loops, best of 3: 1.09 ms per loop
sage: timeit("p(w[4,3,2,1])")
5 loops, best of 3: 95.4 ms per loop
sage: timeit("w(p[4,3,2,1])")
625 loops, best of 3: 1.52 ms per loop
sage:
sage: w = Sym.w(coerce_h=True, coerce_e=True, coerce_p=True)
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 117 µs per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 103 µs per loop
sage: timeit("e(w[4,3,2,1])")
5 loops, best of 3: 94 µs per loop
sage: timeit("w(e[4,3,2,1])")
625 loops, best of 3: 88.2 µs per loop
sage: timeit("s(w[4,3,2,1])")
5 loops, best of 3: 67.6 ms per loop
sage: timeit("w(s[4,3,2,1])")
5 loops, best of 3: 1.47 ms per loop
sage: timeit("p(w[4,3,2,1])")
625 loops, best of 3: 96.8 µs per loop
sage: timeit("w(p[4,3,2,1])")
625 loops, best of 3: 96.6 µs per loop
}}}
It's fun how s(w) is quickest with the e-coercion but the advantage
disappears when all three coercions are on (because it doesn't know where
to go)...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:19>
Comment (by darij):
Can anyone help me understand why the patchbot has been failing to apply
my patch ( http://patchbot.sagemath.org/ticket/14775/ ) ? Have I forgotten
a dependency or does the patchbot start from the combinat queue? (In the
latter case, what is causing a conflict?)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14775#comment:20>