Symmetric functions uses lrcalc in symmetrica and bug fix in skew Schur function indexed by [[], []]

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

This patch switches computations in symmetric functions from symmetric to lrcalc which is now standard package in Sage.

The following code causes a segmentation fault:

sage: s = SFASchur(QQ)
sage: s([[], []])

or

sage: s([]).skew_by(s([]))

which should be s[] but instead causes a segmentation fault.

The calculation of an expansion of a skew Schur function in the Schur basis done with the symmetrica package.

The bug comes from the calculation of a skew Schur function indexed by two empty partitions. To fix this bug we change the computation from the symmetrica package to lrcalc which should be faster and more robust. lrcalc is a package that was integrated into sage in version 5.2.beta1.

Timing tests for computing expansions of skew Schur functions indicate that for large partitions there are significant speed improvements by using lrcalc instead of symmetrica. example: Without this patch applied:

sage: timeit('s([[9,9,8,8,7,7,6,6,5,5,4,3,2,1],[6,5,4,3,2]])')
5 loops, best of 3: 5.06 s per loop

With this patch applied:

sage: timeit('s([[9,9,8,8,7,7,6,6,5,5,4,3,2,1],[6,5,4,3,2]])')            
5 loops, best of 3: 978 ms per loop

• In classical.py the construction of a skew Schur function now calls lrcalc.skew instead of symmetrica.part_part_skewschur

• doc tests were added to check base cases in sfa.py and classical.py

Apply

• attachment: trac_12140-sf_schur_done_w_lrcalc-mz.patch

Depends on #11563

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: sf, days38, sd40

Author: Mike Zabrocki

Reviewer: Anne Schilling

Merged: sage-5.3.beta0

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

[anneschilling]

Reviewer: Anne Schilling

[anneschilling]

Author: Mike Zabrocki, Florent Hivert

[anneschilling]

Changed keywords from sf to sf, days38

[anneschilling]

Description changed:

--- 
+++ 
@@ -11,4 +11,6 @@
 sage: s([]).skew_by(s([]))

-which should be s[] but instead causes the segmentation fault +which should be s[] but instead causes the segmentation fault. + +Apply: attachment: trac_12140_skewschurfix-mz.2.patch

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

bug fix of part_part_skewschur in symmetrica package

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

Description changed:

--- 
+++ 
@@ -13,4 +13,4 @@

 which should be s[] but instead causes the segmentation fault.

-Apply: [attachment: trac_12140_skewschurfix-mz.2.patch](https://github.com/sagemath/sage/files/ticket12140/trac_12140_skewschurfix-mz.2.patch.gz)
+Correct patch is: [attachment: trac_12140_skewschurfix-mz.patch](https://github.com/sagemath/sage-prod/files/10654182/trac_12140_skewschurfix-mz.patch.gz)

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:4

Attachment: trac_12140_skewschurfix-mz.patch.gz

[anneschilling]

Description changed:

--- 
+++ 
@@ -13,4 +13,4 @@

 which should be s[] but instead causes the segmentation fault.

-Correct patch is: [attachment: trac_12140_skewschurfix-mz.patch](https://github.com/sagemath/sage-prod/files/10654182/trac_12140_skewschurfix-mz.patch.gz)
+Apply: [attachment: trac_12140_skewschurfix-mz.patch](https://github.com/sagemath/sage-prod/files/10654182/trac_12140_skewschurfix-mz.patch.gz)

[anneschilling]

Description changed:

--- 
+++ 
@@ -13,4 +13,4 @@

 which should be s[] but instead causes the segmentation fault.

-Apply: [attachment: trac_12140_skewschurfix-mz.patch](https://github.com/sagemath/sage-prod/files/10654182/trac_12140_skewschurfix-mz.patch.gz)
+Apply [attachment: trac_12140_skewschurfix-mz.patch](https://github.com/sagemath/sage-prod/files/10654182/trac_12140_skewschurfix-mz.patch.gz)

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:8

Replying to @anneschilling: Thank you Anne! I love you!

[jdemeyer]

comment:9

This doesn't build on iras (SUSE ES10 ia64):

gcc -fno-strict-aliasing -fwrapv -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -fPIC -I/usr/include/malloc/ -I/home/buildbot/build/sag
e/iras-1/iras_full/build/sage-5.1.beta1/local/include -I/home/buildbot/build/sage/iras-1/iras_full/build/sage-5.1.beta1/local/include/csag
e -I/home/buildbot/build/sage/iras-1/iras_full/build/sage-5.1.beta1/devel/sage/sage/ext -I/home/buildbot/build/sage/iras-1/iras_full/build
/sage-5.1.beta1/local/include/python2.7 -c sage/libs/symmetrica/symmetrica.c -o build/temp.linux-ia64-2.7/sage/libs/symmetrica/symmetrica.
o -w
gcc -pthread -shared -L/home/buildbot/build/sage/iras-1/iras_full/build/sage-5.1.beta1/local/lib build/temp.linux-ia64-2.7/sage/libs/symme
trica/symmetrica.o -L/home/buildbot/build/sage/iras-1/iras_full/build/sage-5.1.beta1/local/lib -L/home/buildbot/build/sage/iras-1/iras_ful
l/build/sage-5.1.beta1/local/lib -lcsage -lsymmetrica -lstdc++ -lntl -lpython2.7 -o build/lib.linux-ia64-2.7/sage/libs/symmetrica/symmetri
ca.so
/usr/bin/ld: /home/buildbot/build/sage/iras-1/iras_full/build/sage-5.1.beta1/local/lib/libsymmetrica.a(vc.o): Can't relax br (PCREL21B) to
 `error_during_computation_code' at 0x1f782 in section `.text' with size 0x81070 (> 0x1000000).
/usr/bin/ld: final link failed: Nonrepresentable section on output
collect2: ld returned 1 exit status
error: command 'gcc' failed with exit status 1

Note:

(sage-sh) buildbot@iras:sage-5.1.beta1$ gcc --version
gcc (GCC) 4.6.3
Copyright (C) 2011 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

(sage-sh) buildbot@iras:sage-5.1.beta1$ ld --version
GNU ld version 2.16.91.0.5 20051219 (SUSE Linux)
Copyright 2005 Free Software Foundation, Inc.
This program is free software; you may redistribute it under the terms of
the GNU General Public License.  This program has absolutely no warranty.

[nthiery]

comment:10

Replying to @jdemeyer:

This doesn't build on iras (SUSE ES10 ia64):

Yikes. Thanks for the report.

Can you confirm that the compilation runs smoothly without the patch? I.e. that this is not an issue of Symmetrica itself?

[anneschilling]

comment:11

Replying to @nthiery:

Replying to @jdemeyer:

This doesn't build on iras (SUSE ES10 ia64):

Yikes. Thanks for the report.

Can you confirm that the compilation runs smoothly without the patch? I.e. that this is not an issue of Symmetrica itself?

Jeroen, since I do not have this linux version at hand, could you please confirm that the compilation runs smoothly without the patch applied?

Thank you,

Anne

[jdemeyer]

comment:12

This is a buildbot machine, so yes, Sage builds and works 100% fine without this patch. I'll be honest that I also have no idea what causes this problem.

[nthiery]

comment:13

Replying to @jdemeyer:

This is a buildbot machine, so yes, Sage builds and works 100% fine without this patch. I'll be honest that I also have no idea what causes this problem.

Ok, I guess we should not waste time and this, and just jump on the occasion to do the right thing, namely to use lrcalc. I just implemented the little changed requested by Jeroen on #11563, so I guess that's ok to add it as a dependency.

What do you think?

[anneschilling]

Changed keywords from sf, days38 to sf, days38, sd40

[anneschilling]

Dependencies: 11563

[anneschilling]

Description changed:

--- 
+++ 
@@ -1,4 +1,6 @@
-The following code causes a segmentation fault:
+This patch switches computations in symmetric functions from symmetric to lrcalc which is now standard package in Sage.
+
+In addition, this patch fixes the following bug which causes a segmentation fault:

sage: s = SFASchur(QQ) @@ -13,4 +15,3 @@

which should be s[] but instead causes the segmentation fault.

-Apply attachment: trac_12140_skewschurfix-mz.patch

[anneschilling]

Changed author from Mike Zabrocki, Florent Hivert to Mike Zabrocki

[kcrisman]

Changed dependencies from 11563 to #11563

[anneschilling]

Description changed:

--- 
+++ 
@@ -1,17 +1,45 @@
 This patch switches computations in symmetric functions from symmetric to lrcalc which is now standard package in Sage.

-In addition, this patch fixes the following bug which causes a segmentation fault:
+The following code causes a segmentation fault:

sage: s = SFASchur(QQ) sage: s([[], []])

+or

-I found this error because I was computing a sum with the skew_by operation
-
-``` 
+```
 sage: s([]).skew_by(s([]))

+which should be s[] but instead causes a segmentation fault.

-which should be s[] but instead causes the segmentation fault. +The calculation of an expansion of a skew Schur function in the Schur +basis done with the symmetrica package.

+The bug comes from the calculation of a skew Schur function indexed +by two empty partitions. To fix this bug we change the computation from the +symmetrica package to lrcalc which should be faster and more robust. +lrcalc is a package that was integrated into sage in version 5.2.beta1. + +Timing tests for computing expansions of skew Schur functions indicate +that for large partitions there are significant speed improvements +by using lrcalc instead of symmetrica. +example: +Without this patch applied: + + +sage: timeit('s([[9,9,8,8,7,7,6,6,5,5,4,3,2,1],[6,5,4,3,2]])') +5 loops, best of 3: 5.06 s per loop + +With this patch applied: + + +sage: timeit('s([[9,9,8,8,7,7,6,6,5,5,4,3,2,1],[6,5,4,3,2]])') +5 loops, best of 3: 978 ms per loop + +- In classical.py the construction of a skew Schur function now calls +lrcalc.skew instead of symmetrica.part_part_skewschur + +- doc tests were added to check base cases in sfa.py and classical.py + +

[anneschilling]

Attachment: trac_12140-sf_schur_done_w_lrcalc-mz.patch.gz

[anneschilling]

comment:17

I tested this patch and it works on my computer. Tests pass. Time claims also hold.

[anneschilling]

Description changed:

--- 
+++ 
@@ -42,4 +42,7 @@

 - doc tests were added to check base cases in sfa.py and classical.py

+__Apply__

+* [attachment: trac_12140-sf_schur_done_w_lrcalc-mz.patch](https://github.com/sagemath/sage-prod/files/10654183/trac_12140-sf_schur_done_w_lrcalc-mz.patch.gz)
+

[jdemeyer]

Merged: sage-5.3.beta0