Opened 11 years ago

Closed 10 years ago

#12140 closed defect (fixed)

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

Reported by: Mike Zabrocki Owned by: Sage Combinat CC user
Priority: major Milestone: sage-5.3
Component: combinatorics Keywords: sf, days38, sd40
Cc: Sage Combinat CC user Merged in: sage-5.3.beta0
Authors: Mike Zabrocki Reviewers: Anne Schilling
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11563 Stopgaps:

Status badges

Description (last modified by Anne Schilling)

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

Attachments (2)

trac_12140_skewschurfix-mz.patch (1.4 KB) - added by Mike Zabrocki 10 years ago.
bug fix of part_part_skewschur in symmetrica package
trac_12140-sf_schur_done_w_lrcalc-mz.patch (3.1 KB) - added by Anne Schilling 10 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 10 years ago by Anne Schilling

Authors: Mike Zabrocki, Florent Hivert
Cc: Sage Combinat CC user added
Reviewers: Anne Schilling

comment:2 Changed 10 years ago by Anne Schilling

Keywords: days38 added

comment:3 Changed 10 years ago by Anne Schilling

Description: modified (diff)
Status: newneeds_review

Changed 10 years ago by Mike Zabrocki

bug fix of part_part_skewschur in symmetrica package

comment:4 Changed 10 years ago by Mike Zabrocki

Description: modified (diff)

comment:5 Changed 10 years ago by Anne Schilling

Description: modified (diff)
Milestone: sage-5.0sage-5.1
Type: PLEASE CHANGEdefect

comment:6 Changed 10 years ago by Anne Schilling

Description: modified (diff)

comment:7 Changed 10 years ago by Anne Schilling

Status: needs_reviewpositive_review

comment:8 in reply to:  7 Changed 10 years ago by Mike Zabrocki

Replying to aschilling: Thank you Anne! I love you!

comment:9 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

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.

comment:10 in reply to:  9 ; Changed 10 years ago by Nicolas M. Thiéry

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?

comment:11 in reply to:  10 Changed 10 years ago by Anne Schilling

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

comment:12 Changed 10 years ago by Jeroen Demeyer

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.

comment:13 in reply to:  12 Changed 10 years ago by Nicolas M. Thiéry

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?

comment:14 Changed 10 years ago by Anne Schilling

Authors: Mike Zabrocki, Florent HivertMike Zabrocki
Dependencies: 11563
Description: modified (diff)
Keywords: sd40 added
Milestone: sage-5.3sage-5.2
Status: needs_workneeds_review
Summary: skew Schur function indexed by [[], []] causes Segmentation FaultSymmetric functions uses lrcalc in symmetrica and bug fix in skew Schur function indexed by [[], []]

comment:15 Changed 10 years ago by Karl-Dieter Crisman

Dependencies: 11563#11563

comment:16 Changed 10 years ago by Anne Schilling

Description: modified (diff)
Milestone: sage-5.2sage-5.3

Changed 10 years ago by Anne Schilling

comment:17 Changed 10 years ago by Anne Schilling

Description: modified (diff)
Status: needs_reviewpositive_review

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

Last edited 10 years ago by Anne Schilling (previous) (diff)

comment:18 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.3.beta0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.