#13762 closed enhancement (fixed)
Implement k-bounded quotient space
Reported by: | chrisjamesberg | Owned by: | chrisjamesberg |
---|---|---|---|
Priority: | major | Milestone: | sage-5.6 |
Component: | combinatorics | Keywords: | symmetric functions, partitions |
Cc: | sage-combinat, saliola, zabrocki, aschilling, tscrim | Merged in: | sage-5.6.beta2 |
Authors: | Chris Berg, Mike Zabrocki | Reviewers: | Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This will implement the k-bounded quotient space, whose basis is indexed by monomial symmetric functions indexed by k-bounded partitions. It is the dual Hopf algebra to the k-bounded subspace where the k-Schur functions live. In doing so, I have also fixed the bug from Ticket #13743.
Attachments (1)
Change History (32)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
- Status changed from new to needs_info
comment:3 Changed 8 years ago by
comment:4 Changed 8 years ago by
comment:5 Changed 8 years ago by
- Status changed from needs_info to needs_review
comment:6 Changed 8 years ago by
- Cc zabrocki aschilling added
- Description modified (diff)
comment:7 Changed 8 years ago by
comment:8 Changed 8 years ago by
comment:10 follow-up: ↓ 11 Changed 8 years ago by
Apply: trac_13762_k_quotient.patch
comment:11 in reply to: ↑ 10 Changed 8 years ago by
Hi Chris,
Thanks for the new patch. I assume this fixes the coercion bug? Did you also fold
- trac_13762_addthis.patch
- trac_13762_possiblefix.patch
that were passed around by e-mail, or should they go after this patch still?
Anne
comment:12 follow-up: ↓ 13 Changed 8 years ago by
- Keywords symmetric functions partitions added
- Reviewers set to Anne Schilling
comment:13 in reply to: ↑ 12 Changed 8 years ago by
This patch implements the K-k-Schur functions and their duals. I tested this code my old private code and it gives the correct answers in the cases I checked.
Chris and Mike, here are a couple more comments I have:
- When building the documentation I get an error
sage/combinat/sf/new_kschur Sphinx error: 'ascii' codec can't decode byte 0xe2 in position 34698: ordinal not in range(128)
- Line 549 of the patch "Returns the symmetric functions. Needed to make TestSuite? work" probably needs to be changed.
- You need an extra line after 650.
- In line 883 of new_kschur (in the patch) the dash is strange
.. [LamSchillingShimozono2010] T. Lam, A. Schilling, M.Shimozono, K-theory Schubert calculus of the affine Grassmannian, 883 Compositio Math. 146 (2010), 811â852.
Also, this reference should probably appear in def K_kschur(self) as well.
- Line 887 """r should read r""" (or remove the r)
So much for now!
Anne
comment:14 follow-up: ↓ 15 Changed 8 years ago by
Anne,
Aren't the documentation error and the dash error related? I replaced the dash and the documentation builds fine on my machine.
Because the patch had changed so much, I didn't know where to put a line after 650, because line 650 had probably changed.
Everything else is fixed. Yes, all the other patches are folded into this.
Apply: trac_13762_k_quotient.patch
comment:15 in reply to: ↑ 14 Changed 8 years ago by
Hi Chris,
Thanks for the changes. The line that should be added is after line 807 in the current version. Other than that it looks good to me. If Mike is also happy, I'll let him set a positive review!
Anne
comment:16 follow-up: ↓ 17 Changed 8 years ago by
- Status changed from needs_review to positive_review
Hi, I am happy with this version of the patch. Chris, thanks for all the work and Anne thanks for the review. -Mike
comment:17 in reply to: ↑ 16 Changed 8 years ago by
There is a problem with the building of the documentation introduced by this patch
reading sources... [100%] structure /Applications/sage-5.5.rc0/local/lib/python2.7/site-packages/sage/combinat/sf/new_kschur.py:docstring of sage.combinat.sf.new_kschur.K_kSchur:9: WARNING: Duplicate explicit target name: "lamschillingshimozono2010". /Applications/sage-5.5.rc0/local/lib/python2.7/site-packages/sage/combinat/sf/new_kschur.py:docstring of sage.combinat.sf.new_kschur.K_kSchur:9: WARNING: duplicate citation LamSchillingShimozono2010, other instance in /Applications/sage-5.5.rc0/devel/sage/doc/en/reference/sage/combinat/sf/new_kschur.rst
I think this needs to be fixed!
Anne
comment:18 follow-up: ↓ 19 Changed 8 years ago by
There was a repeated reference. It should be fixed now.
Apply: trac_13762_k_quotient-2.patch
comment:19 in reply to: ↑ 18 Changed 8 years ago by
Replying to zabrocki:
There was a repeated reference. It should be fixed now.
Apply: trac_13762_k_quotient-2.patch
Looks good now! I leave the positive review.
Anne
comment:20 Changed 8 years ago by
- Status changed from positive_review to needs_work
- Work issues set to don't use assert
There has been a discussion about the usage of "assert" and you should not use "assert" for bad user input, only to check for actual bugs. Bad input should probably give a ValueError
instead.
If there is any way at all to reproduce an AssertionError
using documented public functions, that is by definition a bug.
comment:21 Changed 8 years ago by
Also, the commit message should not be one long line. You should wrap the message in multiple lines, but make sure the first line (which appears in hg log
) makes sense by itself.
comment:22 follow-up: ↓ 23 Changed 8 years ago by
Hi Jeroen,
There are a few 'assert
' lines that we can clearly remove and change to ValueError
, but there is one I am unsure about. Around line 599 in k_dual.py we have
if isinstance(c, Partition_class): assert len(rest) == 0
I don't see how to trigger this. Is it ok to leave it as is?
Some of our assertion errors that appear are triggered in code in free_module.py. Should I change that code here or open a new ticket?
comment:23 in reply to: ↑ 22 Changed 8 years ago by
Replying to zabrocki:
if isinstance(c, Partition_class): assert len(rest) == 0I don't see how to trigger this. Is it ok to leave it as is?
Absolutely. This is how assert
should be used: to say "this condition is always true, without any further assumptions".
Some of our assertion errors that appear are triggered in code in free_module.py. Should I change that code here or open a new ticket?
I don't think you have to change it here, but at least make sure you don't introduce any new wrongly-used asserts.
Changed 8 years ago by
comment:24 follow-up: ↓ 25 Changed 8 years ago by
- Status changed from needs_work to needs_review
OK. Our doctests still raise two assertion errors for calling 'coefficient
' in free_module.py.
comment:25 in reply to: ↑ 24 ; follow-up: ↓ 26 Changed 8 years ago by
Apply: trac_13762_k_quotient.2.patch
comment:26 in reply to: ↑ 25 Changed 8 years ago by
Looks good to me now! I set it back to positive review.
Anne
comment:27 Changed 8 years ago by
- Status changed from needs_review to positive_review
- Work issues don't use assert deleted
comment:28 Changed 8 years ago by
- Cc sage-combinat added
comment:29 Changed 8 years ago by
- Merged in set to sage-5.6.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:30 Changed 8 years ago by
Please read some comments from #12313, which apply to this code:
(tl;dr: your code is badly written and #12313 will make it much slower)
Had a quick look. To simplify and speed up the tests a little bit, you can concentrate on one of the tests that's slow:
sage: cmd='dks4._test_associativity()' sage: import cProfile,pstats sage: s=pstats.Stats(cProfile.Profile().runctx(cmd,globals(),{})) sage: S=s.sort_stats('cumulative') sage: S.print_stats() ... sage: S.print_callers() ...the latter one essentially gives you the call graph, weighted by time contributed.
In fact it shows you pretty quickly that ShurFunctions were apparently VERY heavily relying on parents being cached:
X=dks4[0]+ 2*dks4[1] + 3*dks4[2] (X*X)*X #wait quite a long timeThis mainly uses
dks4.product
and you can follow the code from there to see this has not been written with runtime optimization in mind. Probably if you make some things cached the way there, you'll regain the original performance.My first impression is that this code indeed will make a concrete realization of some structure, perform the operation, and throw away the concrete realization. Elements on the way basically ARE homs, hence all the homsets.
I think the normal behaviour of a CAS should be that a structure S is considered garbage and can be collected, unless the user has constructed some object O and keeps a reference to it, and O keeps a chain of references to S. Sadly, that was not the case for Sage, but this ticket is part of an attempt to make Sage behave "normally" in that department.
Hence, if the same structure is needed repeatedly during a computation, then the programmer should keep a reference to it locally, rather than relying on an external cache. And if different methods of an object O will use the same structure S, then it makes sense to store S as an attribute of O, in order to prevent S from being garbage collected as long as O is alive (but not longer than that).
I think what Nils wanted to say is: If other parts of the Sage library do not obey the general rules formulated in the preceding paragraph, but rely on an infinite external cache, then they need to be fixed. But the need to fix them should not prevent us from changing the infinite external cache to a finite external cache, because that is of benefit for all parts in the Sage library that follow the general rules.
comment:31 Changed 8 years ago by
See #13991 for a follow-up.
Apply: trac_13762_k_quotient.patch