Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#13762 closed enhancement (fixed)

Implement k-bounded quotient space

Reported by: Chris Berg Owned by: Chris Berg
Priority: major Milestone: sage-5.6
Component: combinatorics Keywords: symmetric functions, partitions
Cc: Sage Combinat CC user, Franco Saliola, Mike Zabrocki, Anne Schilling, Travis Scrimshaw 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 Chris Berg)

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 Mike Zabrocki 10 years ago.

Download all attachments as: .zip

Change History (32)

comment:1 Changed 10 years ago by Chris Berg

Last edited 10 years ago by Chris Berg (previous) (diff)

comment:2 Changed 10 years ago by Chris Berg

Status: newneeds_info

comment:3 Changed 10 years ago by Chris Berg

Last edited 10 years ago by Chris Berg (previous) (diff)

comment:4 Changed 10 years ago by Chris Berg

Last edited 10 years ago by Chris Berg (previous) (diff)

comment:5 Changed 10 years ago by Chris Berg

Status: needs_infoneeds_review

comment:6 Changed 10 years ago by Chris Berg

Cc: Mike Zabrocki Anne Schilling added
Description: modified (diff)

comment:7 Changed 10 years ago by Chris Berg

Last edited 10 years ago by Chris Berg (previous) (diff)

comment:8 Changed 10 years ago by Chris Berg

Apply: trac_13762_k_quotient.patch

comment:9 Changed 10 years ago by Travis Scrimshaw

Cc: Travis Scrimshaw added

cc'ed since this conflicts with #13605.

comment:10 Changed 10 years ago by Chris Berg

Apply: trac_13762_k_quotient.patch

comment:11 in reply to:  10 Changed 10 years ago by Anne Schilling

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 Changed 10 years ago by Anne Schilling

Authors: Chris BergChris Berg, Mike Zabrocki
Keywords: symmetric functions partitions added
Reviewers: Anne Schilling

comment:13 in reply to:  12 Changed 10 years ago by Anne Schilling

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 Changed 10 years ago by Chris Berg

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 10 years ago by Anne Schilling

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 Changed 10 years ago by Mike Zabrocki

Status: needs_reviewpositive_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 10 years ago by Anne Schilling

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 Changed 10 years ago by Mike 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 10 years ago by Anne Schilling

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 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work
Work issues: 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 10 years ago by Jeroen Demeyer

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 Changed 10 years ago by Mike 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 10 years ago by Jeroen Demeyer

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 10 years ago by Mike Zabrocki

comment:24 Changed 10 years ago by Mike Zabrocki

Status: needs_workneeds_review

OK. Our doctests still raise two assertion errors for calling 'coefficient' in free_module.py.

comment:25 in reply to:  24 ; Changed 10 years ago by Anne Schilling

Apply: trac_13762_k_quotient.2.patch

comment:26 in reply to:  25 Changed 10 years ago by Anne Schilling

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

Anne

comment:27 Changed 10 years ago by Anne Schilling

Status: needs_reviewpositive_review
Work issues: don't use assert

comment:28 Changed 10 years ago by Anne Schilling

Cc: Sage Combinat CC user added

comment:29 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.6.beta2
Resolution: fixed
Status: positive_reviewclosed

comment:30 Changed 10 years ago by Jeroen Demeyer

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 10 years ago by Jeroen Demeyer

See #13991 for a follow-up.

Note: See TracTickets for help on using tickets.