Addition on CombinatorialFreeModule directly on dictionaries

sagemath / sage

Main repository of SageMath

https://www.sagemath.org

Other

1.33k stars 453 forks source link

Addition on CombinatorialFreeModule directly on dictionaries #9651

Closed stumpc5 closed 13 years ago

stumpc5 commented 14 years ago

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 #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 commented 14 years ago

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

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 14 years ago

comment:2

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

stumpc5 commented 14 years ago

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.patch.gz

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 14 years ago

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 commented 13 years ago

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.2.patch.gz

stumpc5 commented 13 years ago

includes referees suggestions

stumpc5 commented 13 years ago

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.3.patch.gz

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.4.patch.gz

includes more referees suggestions

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 13 years ago

Reviewer: Daniel Bump

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 13 years ago

Description changed:

--- 
+++ 
@@ -7,3 +7,12 @@
 - uses this addition of dictionaries to provide fast methods for CombinatorialFreeModule

 - is (indirectly) based on the patch in Ticket #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.

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 13 years ago

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 commented 13 years ago

comment:6

Please remove * from the commit message

stumpc5 commented 13 years ago

comment:7

Attachment: trac_9651_CombinatorialFreeModule_Addition-cs.5.patch.gz

Replying to @jdemeyer:

Please remove * from the commit message

done!

jdemeyer commented 13 years ago

Merged: sage-4.6.1.alpha0