Opened 2 years ago
Closed 2 years ago
#27050 closed enhancement (fixed)
speed up Schur to fundamental
Reported by: | mantepse | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.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 2 years ago by
- Branch set to u/mantepse/speed_up_schur_to_fundamental
comment:2 Changed 2 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 2 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 2 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 2 years ago by
However, this is a good change to do and is quite a speedup.
comment:6 Changed 2 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 2 years ago by
done, and yes indeed, the _Compositions
was nonsense, thanks!
comment:8 Changed 2 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 2 years ago by
Thanks. Nonsense, because it did not give any speedup with respect to the topic of this ticket.
comment:10 Changed 2 years ago by
- Milestone changed from sage-8.6 to sage-8.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 sage-pending or sage-wishlist.
comment:11 Changed 2 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