#14775 closed enhancement (fixed)

Symmetric functions: Kronecker product over any ring; Kronecker coproduct; antipode over any ring; forgotten basis over any ring; Witt basis; Frobenius and Verschiebung; doc fixes

Reported by: darij Owned by: sage-combinat
Priority: major Milestone: sage-5.12
Component: combinatorics Keywords: symmetric function, combinat, kronecker product, days49
Cc: zabrocki, aschilling, tscrim, nthiery, hivert, sage-combinat, mhansen Merged in: sage-5.12.beta4
Authors: Darij Grinberg Reviewers: Travis Scrimshaw, Mike Zabrocki
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by darij)

This ticket does the following:

  1. The current version of itensor (the Kronecker product on the ring of symmetric function) only works when the ground ring is an algebra over the rationals. This is not a mathematically reasonable restriction. Fix this.
  1. The Kronecker coproduct on the ring of symmetric function has to be implemented. Implement it.
  1. The antipode on the ring of symmetric functions uses coercion into the powersum basis. This means it, too, is not getting computed over arbitrary base rings. Fix this.
  1. The forgotten basis of Symm is defined by duality rather than by explicit formulas. Our duality methods use the powersum basis, again leading to errors for ground rings not being QQ-algebras.
  1. The Witt symmetric functions form another basis of Symm. Implement them.
  1. Implement Frobenius and Verschiebung operations on Symm without recourse to plethysm.

Apply:

Attachments (14)

forgotten-speed-reg1 (1.6 KB) - added by darij 17 months ago.
speed tests before and after goal 4 implementation on partition [4,3,2]
forgotten-speed-reg2 (1.6 KB) - added by darij 17 months ago.
speed tests before and after goal 4 implementation on partition [4,3,2,2]
kronecker-on-Sym.patch (77.7 KB) - added by darij 17 months ago.
backup version, implementing goals 1, 2, 3, 4 of 5
trac_14775-symmetric_functions_extended-dg.patch (199.5 KB) - added by darij 16 months ago.
Finished; please review!
trac_14775-review-ts.patch (193.4 KB) - added by tscrim 15 months ago.
trac_14775-rereview-dg.patch (18.3 KB) - added by darij 15 months ago.
trac_14775-addendum_arith_prod-dg.patch (7.3 KB) - added by darij 15 months ago.
additional method for arithmetic product
trac_14775-qfolded.patch (236.5 KB) - added by darij 15 months ago.
qfold of the previous patches + the changes you suggested
trac_14775-operatorname.patch (810 bytes) - added by darij 15 months ago.
updated (typo fixed)
trac_14775-docstring_tweak-ts.patch (5.6 KB) - added by tscrim 15 months ago.
trac_14775-response-to-mike-dg.patch (125.6 KB) - added by nthiery 15 months ago.
EDIT: now applies correctly
trac_14775_more_review-mz.patch (16.3 KB) - added by zabrocki 15 months ago.
trac_14775-final-changes-dg.patch (2.4 KB) - added by darij 15 months ago.
trac_14775-the_big_crunch.patch (298.2 KB) - added by darij 15 months ago.
qfold of all previous patches in this ticket

Download all attachments as: .zip

Change History (84)

comment:1 Changed 17 months ago by darij

  • Authors set to Darij Grinberg
  • Component changed from PLEASE CHANGE to combinatorics
  • Description modified (diff)
  • Keywords symmetric function combinat kronecker product added
  • Owner changed from tbd to sage-combinat
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 17 months ago by darij

  • Cc zabrocki aschilling tscrim added
  • Description modified (diff)
  • Keywords days49 added

comment:3 Changed 17 months ago by darij

  • Cc nthiery added
  • Description modified (diff)

comment:4 Changed 17 months ago by darij

  • Description modified (diff)
  • Summary changed from Symmetric functions: extending Kronecker product, implementing Kronecker product, extending forgotten basis, implementing Witt basis to Symmetric functions: extending Kronecker product, implementing Kronecker product, extending antipode, extending forgotten basis, implementing Witt basis

comment:5 Changed 17 months ago by darij

3 is done. Anyone has a better name than degree_negation for the algebra automorphism of SymmetricFunctions? which acts as 1 in even degrees and 0 in odd ones?

The changes in the antipode method not only made it work over any rings, but also sped it up on each basis except for the powersum one (and the monomial one, but I improved that with a trivial fix):

Test suite:

def testall():
    Sym = SymmetricFunctions(QQ)
    print "m"
    timeit("SymmetricFunctions(QQ).m()([4,3,2]).antipode()")
    print "h"
    timeit("SymmetricFunctions(QQ).h()([4,3,2]).antipode()")
    print "e"
    timeit("SymmetricFunctions(QQ).e()([4,3,2]).antipode()")
    print "s"
    timeit("SymmetricFunctions(QQ).s()([4,3,2]).antipode()")
    print "p"
    timeit("SymmetricFunctions(QQ).p()([4,3,2]).antipode()")

Results:

original version:

sage: testall()
m
125 loops, best of 3: 1.86 ms per loop
h
25 loops, best of 3: 10.8 ms per loop
e
25 loops, best of 3: 10.8 ms per loop
s
25 loops, best of 3: 30.6 ms per loop
p
625 loops, best of 3: 146 µs per loop

after change of generic antipode to go via omega rather than via coercion to powersum basis:

sage: testall()
m
125 loops, best of 3: 2.16 ms per loop
h
125 loops, best of 3: 2.92 ms per loop
e
125 loops, best of 3: 2.92 ms per loop
s
625 loops, best of 3: 250 µs per loop
p
625 loops, best of 3: 148 µs per loop

after microoptimization in the antipode of powersum (replacing (-1)**blah by case distinction):

sage: testall()             
m
125 loops, best of 3: 1.79 ms per loop
h
125 loops, best of 3: 2.88 ms per loop
e
125 loops, best of 3: 2.95 ms per loop
s
625 loops, best of 3: 252 µs per loop
p
625 loops, best of 3: 113 µs per loop

comment:6 Changed 17 months ago by darij

  • Description modified (diff)

Changed 17 months ago by darij

speed tests before and after goal 4 implementation on partition [4,3,2]

Changed 17 months ago by darij

speed tests before and after goal 4 implementation on partition [4,3,2,2]

comment:7 Changed 17 months ago by darij

New version up, with forgotten functions working over every base ring. I've attached two files which show some timings for conversions from and to f. The times over a base ring which is a QQ-algebra have become a tad worse, although probably not significantly (what are our criteria for that?). The times over a base ring which is a QQ-algebra differ significantly from those over a base ring which is not, although not in a sufficiently consistent way for me to prefer one method over the other.

In other news, this patch has profited much from input by Nicolas Thiery, Mike Zabrocki, Florent Hivert and Simon King. Thank you!

Changed 17 months ago by darij

backup version, implementing goals 1, 2, 3, 4 of 5

comment:8 Changed 17 months ago by darij

If anyone could comment on my witt.py file in trac_14775-symmetric_functions_extended-dg.patch, I'd be much indebted (while the coercions seem to work, my understanding of OOP is still very fragmentary and I wouldn't be surprised if some of what I've done is bad practice). I am going to add more doctests, implement coercions/conversions to power sums and elementary symmetrics. (And if I really have too much time on my hand, I'll add Frobenius and Verschiebung maps.)

comment:9 follow-up: Changed 17 months ago by darij

While there are good formulas for the h, e, p bases in terms of the w bases, as well as not-too-slow algorithms for the w basis in terms of the h, e, p bases (basically by inverting the formulas just mentioned), I am not sure which of them I should implement. Right now I have implemented h-to-w and w-to-h, declaring them as coercions, and p-to-w. The h-to-w and w-to-h coercions use a cache like the ones in dual.py. Now I need guidance on the following:

1) Is it a good idea to also use cache for e-to-w and w-to-e? (The downside is that there will be more caches in memory.) Same for p-to-w (my current implementation is cacheless, thus not as fast as it could be) and w-to-p.

2) If I implement these maps, should I register them as coersions? (This would normally make sense, but I fear they could significantly slow down coercions between standard classical bases because of the asinine way the current system generates coercion paths.)

comment:10 follow-up: Changed 17 months ago by darij

  • Cc hivert sage-combinat added
  • Status changed from new to needs_info

comment:11 in reply to: ↑ 10 Changed 17 months ago by aschilling

Hi Darij,

Could you run some benchmarks to check what happens when you implement and register the above mentioned coercions?

Anne

comment:12 in reply to: ↑ 9 Changed 17 months ago by nthiery

Replying to darij:

1) Is it a good idea to also use cache for e-to-w and w-to-e? (The downside is that there will be more caches in memory.) Same for p-to-w (my current implementation is cacheless, thus not as fast as it could be) and w-to-p.

Only practice will tell, and you'll probably be the one putting this
most to practice; I'd say don't cache for now, and see later if
you need it.

And at some point in the future we would want a mechanism that would
allow the user to specify which caches he want to use for his own
preferred application.

2) If I implement these maps, should I register them as coersions?
(This would normally make sense, but I fear they could significantly
slow down coercions between standard classical bases because of the
asinine way the current system generates coercion paths.)

Go ahead. For most classical basis, Symmetrica provides a direct
conversion, and when there is one the coercion system is not as stupid
as using his depth first search :-)

In any case, if something would need to be fixed, it's the coercion
system, not the usage of coercions as above.

Cheers,

Nicolas

comment:13 Changed 16 months ago by darij

  • Description modified (diff)

Uploading a new version, mostly with docstring fixes. Thanks for your replies, Anne and Nicolas; I'll work on this shortly (haven't returned to the Witt symmetric functions yet).

comment:14 Changed 16 months ago by darij

  • Description modified (diff)
  • Status changed from needs_info to needs_review

comment:15 follow-up: Changed 16 months ago by darij

Done!

@Anne: I've run some benchmarks (which show that caching the coercions to all of the h, e and p bases is a lot better than caching only the one to the h basis). But they don't mean very much since Sage, in the absence of a direct coercion, looks for a compound coercion by depth-first search (which can be, and is in my case, extremely slow). I was too lazy to manually register 2-step coercions, so I went a different way and gave the user the freedom to decide what coercions to cache.

In other news, this patch probably conflicts with every other patch that edits symmetric functions -- sorry.

comment:16 Changed 16 months ago by darij

  • Summary changed from Symmetric functions: extending Kronecker product, implementing Kronecker product, extending antipode, extending forgotten basis, implementing Witt basis to Symmetric functions: Kronecker product over any ring; Kronecker coproduct; antipode over any ring; forgotten basis over any ring; Witt basis; Frobenius and Verschiebung; doc fixes

Changed 16 months ago by darij

Finished; please review!

comment:17 Changed 16 months ago by darij

If you are wondering about the latest change: I removed an obsolete TODO which was already done. Sorry for that being in the patch in the first place.

comment:18 in reply to: ↑ 15 Changed 16 months ago by aschilling

@Anne: I've run some benchmarks (which show that caching the coercions to all of the h, e and p bases is a lot better than caching only the one to the h basis). But they don't mean very much since Sage, in the absence of a direct coercion, looks for a compound coercion by depth-first search (which can be, and is in my case, extremely slow). I was too lazy to manually register 2-step coercions, so I went a different way and gave the user the freedom to decide what coercions to cache.

Darij, could you post the results of your benchmarks?

comment:19 Changed 16 months ago by darij

  • Cc mhansen added

Here's one:

sage: Sym = SymmetricFunctions(QQ)
sage: Sym.inject_shorthands()
/home/darij/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/combinat/sf/sf.py:1174: RuntimeWarning: redefining global value `e`
  inject_variable(shorthand, getattr(self, shorthand)())
sage: w = Sym.w()
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 105 µs per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 103 µs per loop
sage: timeit("e(w[4,3,2,1])")
5 loops, best of 3: 75.5 ms per loop
sage: timeit("w(e[4,3,2,1])")
5 loops, best of 3: 3.26 ms per loop
sage: timeit("s(w[4,3,2,1])")
5 loops, best of 3: 67.6 ms per loop
sage: timeit("w(s[4,3,2,1])")
125 loops, best of 3: 1.73 ms per loop
sage: timeit("p(w[4,3,2,1])")
25 loops, best of 3: 8.5 ms per loop
sage: timeit("w(p[4,3,2,1])")
125 loops, best of 3: 1.88 ms per loop
sage: 
sage: w = Sym.w(coerce_h=False, coerce_p=True)
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 45.4 µs per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 102 µs per loop
sage: timeit("e(w[4,3,2,1])")
5 loops, best of 3: 75.9 ms per loop
sage: timeit("w(e[4,3,2,1])")
5 loops, best of 3: 1.86 ms per loop
sage: timeit("s(w[4,3,2,1])")
5 loops, best of 3: 67.4 ms per loop
sage: timeit("w(s[4,3,2,1])")
5 loops, best of 3: 1.63 ms per loop
sage: timeit("p(w[4,3,2,1])")
625 loops, best of 3: 96.1 µs per loop
sage: timeit("w(p[4,3,2,1])")
625 loops, best of 3: 95.9 µs per loop
sage: 
sage: w = Sym.w(coerce_h=False, coerce_e=True)
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 246 ms per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 1.51 ms per loop
sage: timeit("e(w[4,3,2,1])")
625 loops, best of 3: 88.5 µs per loop
sage: timeit("w(e[4,3,2,1])")
625 loops, best of 3: 87.3 µs per loop
sage: timeit("s(w[4,3,2,1])")
25 loops, best of 3: 9.33 ms per loop
sage: timeit("w(s[4,3,2,1])")
625 loops, best of 3: 1.09 ms per loop
sage: timeit("p(w[4,3,2,1])")
5 loops, best of 3: 95.4 ms per loop
sage: timeit("w(p[4,3,2,1])")
625 loops, best of 3: 1.52 ms per loop
sage: 
sage: w = Sym.w(coerce_h=True, coerce_e=True, coerce_p=True)
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 117 µs per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 103 µs per loop
sage: timeit("e(w[4,3,2,1])")
5 loops, best of 3: 94 µs per loop
sage: timeit("w(e[4,3,2,1])")
625 loops, best of 3: 88.2 µs per loop
sage: timeit("s(w[4,3,2,1])")
5 loops, best of 3: 67.6 ms per loop
sage: timeit("w(s[4,3,2,1])")
5 loops, best of 3: 1.47 ms per loop
sage: timeit("p(w[4,3,2,1])")
625 loops, best of 3: 96.8 µs per loop
sage: timeit("w(p[4,3,2,1])")
625 loops, best of 3: 96.6 µs per loop

It's fun how s(w) is quickest with the e-coercion but the advantage disappears when all three coercions are on (because it doesn't know where to go)...

comment:20 Changed 16 months ago by darij

for the patchbot:

apply trac_14775-symmetric_functions_extended-dg.patch

Last edited 16 months ago by darij (previous) (diff)

Changed 15 months ago by tscrim

comment:21 Changed 15 months ago by tscrim

  • Description modified (diff)
  • Reviewers set to Travis Scrimshaw

Hey Darij,

Here's a review patch which is basically just formatting changes and compacts the implementation of degree_negation(). If you're happy with my changes, you can set this to positive review.

Best,
Travis

Changed 15 months ago by darij

comment:22 Changed 15 months ago by darij

Here's a review of your review. Thanks for the formatting changes which I should have done myself (do you know of a good way to automatically cut the docstring lines to the length they should have, whatever that length is?). Nice work on degree_negation. Most of what I'm fixing in my review is not your errors but mine or old ones.

One thing I've reverted from your review which doesn't seem accidental is "there is no canonical choice for a basis"; this was an abuse of the notion of "canonical". All of the classical bases of Sym are canonical in the sense of category theory (which means "functorial in the ground ring"), and that's really the only formal meaning of this notion in mathematics. Apparently "canonical" was meant as "clearly more natural than the others", but that's imprecise and subjective. IMHO "it does not come with a basis already chosen" reflects better what is happening.

Last edited 15 months ago by darij (previous) (diff)

comment:23 Changed 15 months ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 15 months ago by darij

additional method for arithmetic product

comment:24 Changed 15 months ago by darij

I've just added a new attachment trac_14775-addendum_arith_prod-dg.patch with a new method for the arithmetic product ( http://mathoverflow.net/questions/138148 ). Sorry for straining you more, Travis; if you wish, I can move this to a new ticket.

So far, for the patchbot:

apply trac_14775-symmetric_functions_extended-dg.patch trac_14775-review-ts.patch trac_14775-rereview-dg.patch​ trac_14775-addendum_arith_prod-dg.patch

Last edited 15 months ago by darij (previous) (diff)

comment:25 Changed 15 months ago by tscrim

Hey Darij,

Sorry I didn't get back to you yesterday. I don't like the phrasing you used (and canonical to me means there is a clear/special reason why this basis is "better" than the others). How about something like

1 - "there is no natural choice for a basis",

2 - "there are multiple natural bases"?

Looking at the arithmetic product (which should go here I think), I have some suggestions:

  • The math equation on line 2842, could you set it in a .. MATH:: block?
  • I think the OUTPUT block should be a sentence (it really just needs to be capitalized and have a period).
  • Remove the else on line 2929 since it makes the code more clear (at least to me since the function ends on the same indent level it started at; and do the de-indent of course).
  • Remove some of the comments, in particular the ones describing the variables in the for loops since they are cluttering up the code IMO.

Last, could you fold all of the patches into a single patch? This will make it easier for me to do the final review.

Thank you,
Travis

Changed 15 months ago by darij

qfold of the previous patches + the changes you suggested

comment:26 Changed 15 months ago by darij

Hi Travis,

agreeing with phrasing 2 and all the suggestions. Done!

Best regards,
Darij

patchbot:

apply trac_14775-qfolded.patch​

Last edited 15 months ago by darij (previous) (diff)

comment:27 Changed 15 months ago by darij

  • Description modified (diff)

comment:28 Changed 15 months ago by tscrim

  • Status changed from needs_review to positive_review

Looks good to me now. Thanks Darij.

comment:29 Changed 15 months ago by darij

Thanks for reviewing this monster!!

comment:30 Changed 15 months ago by tscrim

  • Description modified (diff)

I noticed a minor docstring problem I missed (and introduced). Here's a small review patch which does the necessary tweak.

For patchbot:

Apply: trac_14775-qfolded.patch​, trac_14775-docstring_tweak-ts.patch

comment:31 Changed 15 months ago by jdemeyer

  • Status changed from positive_review to needs_work

PDF documentation doesn't build:

! Undefined control sequence.
<argument> ...imits _{i \geq 1, j \geq 1} p_{\lcm 
                                                  (\lambda _i, \mu _j)}^{\gc...
l.82512 \end{gather}

? ]]
! Emergency stop.
<argument> ...imits _{i \geq 1, j \geq 1} p_{\lcm 
                                                  (\lambda _i, \mu _j)}^{\gc...
l.82512 \end{gather}

!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on combinat.log.
 [8make[1]: *** [combinat.pdf] Error 1

comment:32 Changed 15 months ago by darij

  • Status changed from needs_work to positive_review

IMHO this is more an issue with the PDF docbuilder... \gcd and \lcm are standard commands.

Does it build fine with trac_14775-operatorname.patch? I can't check docbuild pdf at all on my system.

Changed 15 months ago by darij

updated (typo fixed)

comment:33 Changed 15 months ago by jdemeyer

  • Status changed from positive_review to needs_work

comment:34 Changed 15 months ago by jdemeyer

  • Status changed from needs_work to needs_review

Needs review (not my job, sorry...)

Changed 15 months ago by tscrim

comment:35 Changed 15 months ago by tscrim

Here's a new version of my tweak patch which builds the pdf:

Build finished.  The built documents can be found in /home/travis/sage-5.11.rc0/devel/sage/doc/output/pdf/en/reference/combinat

Darij, unfortunately \lcm and \gcd are actually not standard latex commands (as counter-intuitive as it is). See here. I changed them instead to \mathrm{lcm} and made another tweak that was causing the pdf builder to fail. If you're happy with my changes, go ahead and set this to positive review.

Best,
Travis

comment:36 Changed 15 months ago by darij

  • Status changed from needs_review to positive_review

Thanks and good work finding the typos!

comment:37 Changed 15 months ago by zabrocki

  • Status changed from positive_review to needs_work

I have a couple of comments before the final positive review

  • I ran pyflakes and found (some of these could be from previous patches)
    sage/combinat/sf/elementary.py:236: redefinition of unused 'Partition' from line 21
    sage/combinat/sf/powersum.py:334: redefinition of unused 'Partition' from line 21
    sage/combinat/sf/powersum.py:456: redefinition of unused 'Partition' from line 21
    sage/combinat/sf/schur.py:433: 'Partition' imported but unused
    sage/combinat/sf/sfa.py:802: local variable 'result' is assigned to but never used
    sage/combinat/sf/sfa.py:2916: 'Partitions' imported but unused
    sage/combinat/sf/sfa.py:2917: 'divisors' imported but unused
    sage/combinat/sf/witt.py:20: 'classical' imported but unused
    sage/combinat/sf/witt.py:22: 'QQ' imported but unused
    sage/combinat/sf/witt.py:22: 'ZZ' imported but unused
    sage/combinat/sf/witt.py:1309: redefinition of unused 'Integer' from line 22
    
  • in the documentation of verschiebung in witt.py line 1294 and elementary.py line 223 and powersum.py line 443 :

same result as the implementation in sfa.py on the monomial

The tests seem to be on complete homogeneous. Is monomial a typo?

  • There are a number of whitespace issues in the files that I looked at (e.g. witt.py, dual.py). Please check these carefully.
  • for the method frobenius add a ... SEEALSO: :meth:`plethysm` and similarly in plethsym add a SEEALSO for frobenius. The problem with the name frobenius is that it is not at all descriptive (because there are other things that are named after Frobenius e.g. at one time the documentation had Frobenius omega automorphism, but I am more thinking the map that is more commonly called the Frobenius map from the ring of characters to the symmetric functions). Can I request that you use adams_operator or something like this instead?
  • I don't want to undo if what you already tried, but in elementary.py I see:

(coeff if (sum(lam) - Integer(sum(lam) / n)) % 2 == 0 else -coeff)

is 1 if x%2==0 else -1 this faster than (-1)**x in this case? I tried experiments like timeit('[(-1)**v for v in range(1000)]') vs. timeit('[(1 if v%2==0 else -1) for v in range(1000)]') and the former was faster. Try:

(-1)**((sum(lam) - Integer(sum(lam) / n)) % 2)*coeff

or to avoid computing the sum twice

(-1)**((lambda v: (v-Integer(v/n))%2)(sum(lam)))*coeff

comment:38 Changed 15 months ago by darij

Thanks for looking into that code! I'm fixing the issues now. But what exactly do you mean by whitespace issues? Do you have a handy regex for searching for them?

EDIT: adams_operation is now an alias for frobenius; good point! I don't want to remove frobenius, though, as it is a natural name from the Witt vector viewpoint. The other Frobenius map (the characteristic map) has a different domain, so no confusion can arise. The omega map I've never seen named after Frobenius outside of the code.

Last edited 15 months ago by darij (previous) (diff)

comment:39 Changed 15 months ago by zabrocki

I always search for them by looking for <tab> and <space><newline>. On the editor I use it is '\t' and ' \r'

comment:40 Changed 15 months ago by tscrim

It seems like there is something special happening for negative numbers / 1 / -1:

sage: %timeit (-1)**1000
1000000 loops, best of 3: 993 ns per loop
sage: %timeit (-1)**2000                    
100000 loops, best of 3: 968 ns per loop
sage: %timeit (-1)**5000
1000000 loops, best of 3: 924 ns per loop
sage: %timeit (-1)**10000
100000 loops, best of 3: 881 ns per loop

It probably is doing an if/then via modulus for "large" powers. So having it as (-1)**x is faster. Good caveat to know.

I agree that we should avoid doing the sum twice, but it's faster to store it as a variable instead of a lambda function:

sage: y = lambda a: 5
sage: %timeit y(2)
1000000 loops, best of 3: 770 ns per loop
sage: %timeit x = 5; x
1000000 loops, best of 3: 336 ns per loop

Any doc typos are my fault from copy/pasting.

Thanks for the comments Mike.

Best,
Travis

comment:41 Changed 15 months ago by darij

Thanks!

About (-1)**a * x vs. x if a % 2 == 0 else -x: I've changed it to the former (= more intuitive) syntax now in the Verschiebung method. I was getting a speedup from the latter syntax in a different method (omega or antipode, I don't remember), which made me adapt it as a general tactic. I guess Python is smarter than that, though. Either way the time difference is small and tends to hide behind noise (my firefox is running), and I'm not sure whether it is due to the exponentiation itself or to the fact that the former syntax coerces (-1)**a into the parent of x and then does multiplication within that parent, while the latter only ever uses negation in the parent of x.

Uploading file now...

comment:42 Changed 15 months ago by darij

Done. Someone (Mike? Travis?) should take a look at this as I've been making a lot of manual whitespace changes and who knows whether they're really all whitespace. ;)

patchbot:

apply trac_14775-qfolded.patch​ trac_14775-docstring_tweak-ts.patch​ trac_14775-response-to-mike-dg.patch​

Last edited 15 months ago by darij (previous) (diff)

comment:43 Changed 15 months ago by darij

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:44 Changed 15 months ago by jdemeyer

  • Status changed from needs_review to needs_work

Please do not make whitespace changes to code you otherwise don't touch. It can only lead to merge conflicts and doesn't really benefit anyone. When you change code or add new code, it would be good not to have trailing whitespace. But that's no excuse for changing whitespace all over the place.

comment:45 follow-up: Changed 15 months ago by darij

OK, Jeroen, you tell me what files should be removed from the patch. No offense but I'm tired of following unwritten rules. Currently, every file changed by this patch is changed in a nontrivial way (not only whitespaces), although in three cases (jack.py, kfpoly.py, macdonald.py) it is all cosmetics (typos fixed in the doc). In all the other cases the changes are more substantial (e. g., wrong docstring rewritten). I have no idea what is the threshold for a change you consider beneficial.

comment:46 in reply to: ↑ 45 Changed 15 months ago by jdemeyer

Replying to darij:

I have no idea what is the threshold for a change you consider beneficial.

The threshhold is easy: anything that is not purely a trailing-whitespace change. Fixing typos is good, rewriting docstrings is good, changing non-trailing whitespace (in a PEP-8 compliant way) is good.

I seem to recall that the git workflow will ignore trailing spaces anyway, so the "problem" will disappear anyway.

comment:47 follow-up: Changed 15 months ago by darij

Fine -- am I seeing it right that there is nothing to change then, because every file has got more substantial changes than just trailing whitespace?

comment:48 in reply to: ↑ 47 Changed 15 months ago by jdemeyer

Replying to darij:

Fine -- am I seeing it right that there is nothing to change then, because every file has got more substantial changes than just trailing whitespace?

Well, the first file in trac_14775-response-to-mike-dg.patch, sage/combinat/sf/classical.py, seems to have only trailing-whitespace changes. Moreover, it's not just a matter of "which file". Making a one-character change in a given file does not suddenly mean that you should remove all trailing whitespace in that file.

comment:49 follow-up: Changed 15 months ago by darij

OK, I can revert classical.py. For some reason I thought I changed it in the old patch, but I didn't.

About the rest: Well, sorry, but I'll need a more precise statement of what changes should be reverted if I'm to revert anything. What is your quantum -- if not a file, a class? a method? That said, I'm not convinced the theoretical possibility of conflicts in this particular case justifies causing Mike and me more trouble (Mike is apparently writing a followup patch to this, if I got his email right) and delaying this even further. I've taken notice of the general rule about whitespaces now, but apply it retroactively seems just as much a pain in the ass as what it is trying to prevent.

Last edited 15 months ago by darij (previous) (diff)

comment:50 in reply to: ↑ 49 ; follow-up: Changed 15 months ago by jdemeyer

  • Status changed from needs_work to positive_review

Replying to darij:

What is your quantum -- if not a file, a class? a method?

A method at most (even less for "big" methods which I admit is not well-defined).

That said, I'm not convinced the theoretical possibility of conflicts in this particular case justifies causing Mike and me more trouble (Mike is apparently writing a followup patch to this, if I got his email right) and delaying this even further. I've taken notice of the general rule about whitespaces now, but apply it retroactively seems just as much a pain in the ass as what it is trying to prevent.

Fair enough, restoring positive review.

comment:51 Changed 15 months ago by darij

Thank you!!

comment:52 in reply to: ↑ 50 ; follow-up: Changed 15 months ago by nthiery

Replying to jdemeyer:

Replying to darij:

What is your quantum -- if not a file, a class? a method?

A method at most (even less for "big" methods which I admit is not well-defined).

My rule of thumb is that, if I change a given line and see a trivial thing to fix in the couple neighbour lines, I go ahead, and otherwise leave it alone.

comment:53 in reply to: ↑ 52 Changed 15 months ago by jdemeyer

Replying to nthiery:

My rule of thumb is that, if I change a given line and see a trivial thing to fix in the couple neighbour lines, I go ahead, and otherwise leave it alone.

Yes, that sounds right.

comment:54 Changed 15 months ago by nthiery

  • Dependencies set to #14866

Changed 15 months ago by nthiery

EDIT: now applies correctly

comment:55 Changed 15 months ago by nthiery

For the record: I removed to trivial whitespace fixes from trac_14775-response-to-mike-dg.patch which were already handled by #14866 and created a conflict. I allowed myself to leave the positive review.

comment:56 Changed 15 months ago by darij

Applies correctly on top of #14866; thank you very much!

comment:57 Changed 15 months ago by tscrim

  • Dependencies #14866 deleted

Currently this causes a (very small) conflict with #14102 (which depends on #10963). Should we:

  • revert the changes in this patch around where the conflict occurs (approx. line 826-830)?
  • remove the changes in ns_macdonald.py to a ticket depending on #14102?
  • rebase #14102?

comment:58 Changed 15 months ago by darij

nthiery has just rebased #14102, hasn't he?

comment:59 Changed 15 months ago by tscrim

Yep. Thanks Nicolas.

Changed 15 months ago by zabrocki

comment:60 Changed 15 months ago by zabrocki

  • Description modified (diff)
  • Status changed from positive_review to needs_work

I added a number of doc changes consisting of mostly cleaning up references, a few missing colons, some extra imports caught by pyflakes, corrections of broken links, etc. Please check my changes again carefully.

comment:61 Changed 15 months ago by zabrocki

  • Status changed from needs_work to needs_review

Changed 15 months ago by darij

comment:62 Changed 15 months ago by darij

The changes are good except for one typo you can't help making. I have fixed the typo and added a couple more docstring changes. Once you've looked into them, this is positive_review, right?

patchbot:

apply trac_14775-qfolded.patch​ trac_14775-docstring_tweak-ts.patch​ trac_14775-response-to-mike-dg.patch​ trac_14775_more_review-mz.patch trac_14775-final-changes-dg.patch

comment:63 Changed 15 months ago by darij

  • Description modified (diff)
  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Mike Zabrocki

comment:64 Changed 15 months ago by tscrim

I'm good with the changes. If Mike is also happy with the final version of the patch, Darij, could you fold all of the patches together? Thanks.

comment:65 Changed 15 months ago by zabrocki

  • Status changed from needs_review to positive_review

You'd think that doing that twice that it was on purpose, but it isn't! Mea culpa!

I approve.

comment:66 Changed 15 months ago by darij

  • Description modified (diff)

comment:67 Changed 15 months ago by darij

Thanks again, everyone!

patchbot:

apply trac_14775-the_big_crunch.patch

comment:68 Changed 15 months ago by jdemeyer

  • Status changed from positive_review to needs_work

Sorry, but all changesets qfolded is not a good commit message, it doesn't describe what the patch does.

Changed 15 months ago by darij

qfold of all previous patches in this ticket

comment:69 Changed 15 months ago by darij

  • Status changed from needs_work to positive_review

Commit message fixed.

comment:70 Changed 14 months ago by jdemeyer

  • Merged in set to sage-5.12.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.