Addition on CombinatorialFreeModule directly on dictionaries

[stumpc5]

At the moment, adding (and taking negative, substracting,...) for CombinatorialFreeModule is not done in a very efficient way.

This patch

• provides a cythonized version of a pointwise addition of dictionaries, together with multiple options

• uses this addition of dictionaries to provide fast methods for CombinatorialFreeModule

• is (indirectly) based on the patch in Ticket New feature: ModulesWithBasis allows module_morphism's to a wider class of codomains #9648

======================================

prerequisite:
trac_9648_modulemorphism_codomain_extension.2.patch

apply that patch and
trac_9651_CombinatorialFreeModule_Addition-cs.4.patch,
which supercedes the previously posted patches on this page.

Component: combinatorics

Keywords: addition of dictionaries, CombinatorialFreeModule

Author: Christian Stump

Reviewer: Daniel Bump

Merged: sage-4.6.1.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/9651

[stumpc5]

comment:1

Attachment: trac_9651_CombinatorialFreeModule_Addition.patch.gz

The patch still needs some doctesting (I have not yet done much, but will do more these days) - in particular, I modified CombinatorialFreeModule._apply_module_morphism and .apply_module_endomorphism. The first method is used in the code for symmetric functions: powersum.py, sfa.py and macdonald.py. Would be nice if someone could check if everything there still works well.

Thx, Christian

[dwbump]

comment:2

The patch doesn't apply cleanly to sage-4.5.3.rc0. Applying #9648 first doesn't help.

[stumpc5]

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.patch.gz

[dwbump]

comment:3

The revised patch trac_9651_CombinatorialFreeModule_Addition-cs.patch
applies cleanly to sage 4.6.alpha1 and passes all tests.

But I haven't been able to confirm that it is a speedup. The results
of some testing are here:

http://groups.google.com/group/sage-combinat-devel/msg/4869cc885ca42bc1

[stumpc5]

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.2.patch.gz

[stumpc5]

includes referees suggestions

[stumpc5]

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.3.patch.gz

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.4.patch.gz

includes more referees suggestions

[dwbump]

Reviewer: Daniel Bump

[dwbump]

comment:4

Positive review!

There is a thread about this patch in sage-combinat-devel
resulting in the latest version.

I tested this with sage-4.6.alpha3. After applying

trac_9648_modulemorphism_codomain_extension.2.patch 
trac_9651_CombinatorialFreeModule_Addition-cs.4.patch

all tests pass. I also confirmed that the test is a speedup.

[jdemeyer]

comment:6

Please remove * * * from the commit message

[stumpc5]

comment:7

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.5.patch.gz

Replying to @jdemeyer:

Please remove * * * from the commit message

done!

[jdemeyer]

Merged: sage-4.6.1.alpha0