Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#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:

Status badges

Description (last modified by chrisjamesberg)

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)

trac_13762_k_quotient.2.patch (104.9 KB) - added by zabrocki 8 years ago.

Download all attachments as: .zip

Change History (32)

comment:1 Changed 8 years ago by chrisjamesberg

Last edited 8 years ago by chrisjamesberg (previous) (diff)

comment:2 Changed 8 years ago by chrisjamesberg

  • Status changed from new to needs_info

comment:3 Changed 8 years ago by chrisjamesberg

Last edited 8 years ago by chrisjamesberg (previous) (diff)

comment:4 Changed 8 years ago by chrisjamesberg

Last edited 8 years ago by chrisjamesberg (previous) (diff)

comment:5 Changed 8 years ago by chrisjamesberg

  • Status changed from needs_info to needs_review

comment:6 Changed 8 years ago by chrisjamesberg

  • Cc zabrocki aschilling added
  • Description modified (diff)

comment:7 Changed 8 years ago by chrisjamesberg

Last edited 8 years ago by chrisjamesberg (previous) (diff)

comment:8 Changed 8 years ago by chrisjamesberg

Apply: trac_13762_k_quotient.patch

comment:9 Changed 8 years ago by tscrim

  • Cc tscrim added

cc'ed since this conflicts with #13605.

comment:10 follow-up: Changed 8 years ago by chrisjamesberg

Apply: trac_13762_k_quotient.patch

comment:11 in reply to: ↑ 10 Changed 8 years ago by aschilling

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: Changed 8 years ago by aschilling

  • Authors changed from Chris Berg to Chris Berg, Mike Zabrocki
  • Keywords symmetric functions partitions added
  • Reviewers set to Anne Schilling

comment:13 in reply to: ↑ 12 Changed 8 years ago by aschilling

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: Changed 8 years ago by chrisjamesberg

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 aschilling

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: Changed 8 years ago by zabrocki

  • 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 aschilling

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: Changed 8 years ago by zabrocki

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 aschilling

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 jdemeyer

  • 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 jdemeyer

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: Changed 8 years ago by zabrocki

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 jdemeyer

Replying to zabrocki:

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?

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 zabrocki

comment:24 follow-up: Changed 8 years ago by zabrocki

  • 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: Changed 8 years ago by aschilling

Apply: trac_13762_k_quotient.2.patch

comment:26 in reply to: ↑ 25 Changed 8 years ago by aschilling

Looks good to me now! I set it back to positive review.

Anne

comment:27 Changed 8 years ago by aschilling

  • Status changed from needs_review to positive_review
  • Work issues don't use assert deleted

comment:28 Changed 8 years ago by aschilling

  • Cc sage-combinat added

comment:29 Changed 8 years ago by jdemeyer

  • 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 jdemeyer

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 time

This 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 jdemeyer

See #13991 for a follow-up.

Note: See TracTickets for help on using tickets.