Opened 3 years ago
Closed 3 years ago
#27050 closed enhancement (fixed)
speed up Schur to fundamental
Reported by:  mantepse  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  combinatorics  Keywords:  
Cc:  zabrocki, tscrim, darij  Merged in:  
Authors:  Martin Rubey  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  891a1f0 (Commits, GitHub, GitLab)  Commit:  891a1f020725e494ccde9dfc3c9a70de6479d083 
Dependencies:  Stopgaps: 
Description (last modified by )
Old:
sage: s = SymmetricFunctions(QQ).schur() sage: F = QuasiSymmetricFunctions(QQ).Fundamental() sage: %timeit [F(s(la)) for la in Partitions(7)] 1 loop, best of 3: 2.04 s per loop sage: %timeit [F(s(la)) for la in Partitions(8)] 1 loop, best of 3: 8.8 s per loop
New:
sage: s = SymmetricFunctions(QQ).schur() sage: F = QuasiSymmetricFunctions(QQ).Fundamental() sage: %timeit [F(s(la)) for la in Partitions(7)] 10 loops, best of 3: 97.9 ms per loop sage: %timeit [F(s(la)) for la in Partitions(8)] 1 loop, best of 3: 331 ms per loop
Change History (11)
comment:1 Changed 3 years ago by
 Branch set to u/mantepse/speed_up_schur_to_fundamental
comment:2 Changed 3 years ago by
 Cc zabrocki tscrim darij added
 Commit set to dc41651a32d48ab376ef6671d16ad5fc6c4d6b1e
 Component changed from PLEASE CHANGE to combinatorics
 Description modified (diff)
 Status changed from new to needs_review
 Type changed from PLEASE CHANGE to enhancement
comment:3 Changed 3 years ago by
 Commit changed from dc41651a32d48ab376ef6671d16ad5fc6c4d6b1e to 068d937fc441ca4bfe28636afb507fe766f8d868
Branch pushed to git repo; I updated commit sha1. New commits:
068d937  fix wrong replacements

comment:4 Changed 3 years ago by
 Status changed from needs_review to needs_work
With _Partitions
/Partitions()
, we decided to make that a global object permanently fixed in memory because it appears in so many different contexts within combinatorics and could appear in tighter loops (e.g., the cycle type of a permutation). So I am not sure about doing the same for _Combinations
/Combinations()
. Moreover, it should not have such a significant impact on timings because of the UniqueRepresentation
behavior. Thus, I think this is something we need to take into more careful consideration. Nevertheless, it should be something on an independent ticket because it is a bigger change.
In _from_schur_on_basis
, you can (I would probably even say should) use self._indices
instead of Compositions()
as self._indices
has a little more context.
comment:5 Changed 3 years ago by
However, this is a good change to do and is quite a speedup.
comment:6 Changed 3 years ago by
 Branch changed from u/mantepse/speed_up_schur_to_fundamental to u/mantepse/speedup_schur_to_fundamental
 Commit changed from 068d937fc441ca4bfe28636afb507fe766f8d868 to 891a1f020725e494ccde9dfc3c9a70de6479d083
 Status changed from needs_work to needs_review
comment:7 Changed 3 years ago by
done, and yes indeed, the _Compositions
was nonsense, thanks!
comment:8 Changed 3 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
I wouldn't say it was nonsense, but just something that would warrant a little more consideration.
Anyways, LGTM. Thanks.
comment:9 Changed 3 years ago by
Thanks. Nonsense, because it did not give any speedup with respect to the topic of this ticket.
comment:10 Changed 3 years ago by
 Milestone changed from sage8.6 to sage8.7
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sagepending or sagewishlist.
comment:11 Changed 3 years ago by
 Branch changed from u/mantepse/speedup_schur_to_fundamental to 891a1f020725e494ccde9dfc3c9a70de6479d083
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
add dedicated coercion from the Schur basis to the Fundamental basis