#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) Commit: 891a1f020725e494ccde9dfc3c9a70de6479d083
Dependencies: Stopgaps:

Description (last modified by mantepse)

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 17 months ago by mantepse

  • Branch set to u/mantepse/speed_up_schur_to_fundamental

comment:2 Changed 17 months ago by mantepse

  • Authors set to Martin Rubey
  • 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

New commits:

dc41651add dedicated coercion from the Schur basis to the Fundamental basis

comment:3 Changed 17 months ago by git

  • Commit changed from dc41651a32d48ab376ef6671d16ad5fc6c4d6b1e to 068d937fc441ca4bfe28636afb507fe766f8d868

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

068d937fix wrong replacements

comment:4 Changed 17 months ago by tscrim

  • 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 17 months ago by tscrim

However, this is a good change to do and is quite a speedup.

comment:6 Changed 17 months ago by mantepse

  • 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 17 months ago by mantepse

done, and yes indeed, the _Compositions was nonsense, thanks!

comment:8 Changed 17 months ago by tscrim

  • 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 17 months ago by mantepse

Thanks. Nonsense, because it did not give any speedup with respect to the topic of this ticket.

comment:10 Changed 17 months ago by embray

  • 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 16 months ago by vbraun

  • Branch changed from u/mantepse/speedup_schur_to_fundamental to 891a1f020725e494ccde9dfc3c9a70de6479d083
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.