Restrict skew partition input to Schur basis and implement a skew Schur method

[tscrim]

If you pass a skew partition to a basis of the symmetric functions, you get what should be the skew Schur function:

sage: sp = SkewPartition([[5,3,3,1], [3,2,1]])
sage: e = SymmetricFunctions(QQ).e()
sage: e(sp)
e[2, 2, 1, 1] + e[2, 2, 2] + e[3, 1, 1, 1] + 3*e[3, 2, 1] + e[3, 3] + 2*e[4, 1, 1] + 2*e[4, 2] + e[5, 1]

This would be corresponding skew Schur function if it was in the Schur basis, however we have

sage: s = SymmetricFunctions(QQ).s()
sage: e(s(sp))
e[2, 1, 1, 1, 1] - e[2, 2, 1, 1] - e[3, 1, 1, 1] + e[3, 2, 1]

This ticket will make skew partition input only valid for Schur functions and implement a method skew_schur which handles creating skew Schur functions.

CC: @sagetrac-sage-combinat @nthiery @zabrocki @darijgr @anneschilling

Component: combinatorics

Keywords: schur, symmetric functions

Author: Travis Scrimshaw

Branch/Commit: 14e6047

Reviewer: Anne Schilling, Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/19218

[tscrim]

comment:1

While I was at it, there were a couple of other things I tweaked. Most of these were done because of my initial changes broke something else small. (I was able to clean up a little bit of Sage's import hell.)

I simplified the _element_constructor_ for the bases in order to get the error message I want and those two cases are both handled by R(x) and in cython:

sage: s = SymmetricFunctions(QQ).s()
sage: %timeit s(5)
The slowest run took 86.46 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 2.95 µs per loop
sage: %timeit s(5/2)
The slowest run took 21.65 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 3.15 µs per loop

versus previously

sage: %timeit s(5)
The slowest run took 248.01 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 3.04 µs per loop
sage: %timeit s(5/2)
The slowest run took 20.99 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 3.19 µs per loop

So a marginal speed gain, but still a gain of ~2% (and much more simple code structure).

Additionally I made a few changes of Partition(x) to _Partitions(x) because it is slightly faster, which matters in these tight loops:

sage: from sage.combinat.partition import _Partitions
sage: %timeit Partition([7,5,5,3,2,1,1])
The slowest run took 203.43 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 13.9 µs per loop
sage: %timeit _Partitions([7,5,5,3,2,1,1])
The slowest run took 11.24 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 13.3 µs per loop

sage: %timeit _Partitions([7,5,5,3,2,1,1,0,0])
The slowest run took 5.16 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 15.9 µs per loop
sage: %timeit Partition([7,5,5,3,2,1,1,0,0])
The slowest run took 4.42 times longer than the fastest. This could mean that an intermediate result is being cached 
10000 loops, best of 3: 16.7 µs per loop

We should probably make this change in the rest of the code in other parts of combinat, especially the SF code as this is usually called frequently.

---

New commits:

fee5688

Fixing skew Schur functions and some other misc tweaks.

[tscrim]

Commit: fee5688

[tscrim]

Branch: public/combinat/skew_schur-19218

[darijgr]

comment:2

+            s = self.realization_of().schur()
+            from sage.combinat.skew_partition import SkewPartitions
+            import sage.libs.lrcalc.lrcalc as lrcalc
+            if x not in SkewPartitions():
+                raise ValueError("not a valid skew partition")

Shouldn't the if-check be before the other instructions? Maybe even in the element constructor, before calling the skew_schur function, seeing that Python is usually slow at handling exceptions?

Other than this, the patch looks good if someone can check that (1) elements of the base ring and elements coercing into the base ring still coerce OK (please check on various bases), and (2) the doctests pass. (I don't have time to fire up Sage...) Glad you caught this bug, Travis!

[sagetrac-git]

Changed commit from fee5688 to 14e6047

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

14e6047

Reordering skew_schur for speed.

[tscrim]

comment:4

Replying to @darijgr:

Shouldn't the if-check be before the other instructions?

Good point, done.

Maybe even in the element constructor, before calling the skew_schur function, seeing that Python is usually slow at handling exceptions?

This is the first thing that is checked in the element constructor. This is the first thing that is checked by the Schur functions element constructor, and exception generation and handling is faster than checking if something is a skew partition a second time. Although if you really want speed, you probably shouldn't use the element constructor (as that also goes through the coercion framework first).

Other than this, the patch looks good if someone can check that (1) elements of the base ring and elements coercing into the base ring still coerce OK (please check on various bases), and (2) the doctests pass. (I don't have time to fire up Sage...) Glad you caught this bug, Travis!

Chances are I could probably remove the coercion of elements into the base ring because that should be handled by the coercion framework beforehand (as this is the conversion step). However that seemed too likely to be a can of worms for me to change it here...

[anneschilling]

comment:5

The patch looks good to me. Thanks for fixing the bug, Travis!

[anneschilling]

Reviewer: Anne Schilling, Darij Grinberg

[tscrim]

comment:7

Thanks to both.

[vbraun]

Changed branch from public/combinat/skew_schur-19218 to 14e6047