#18447: Implement dual-quasi-Schur basis in NCSF
-------------------------------------+-------------------------------------
Reporter: zabrocki | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.7
Component: combinatorics | Resolution:
Keywords: ncsf, qsym, | Merged in:
quasiSchur, quasisymmetric | Reviewers: Travis Scrimshaw
Authors: Mike Zabrocki | Work issues:
Report Upstream: N/A | Commit:
Branch: | 217e24b7d0c024cf52b4bdc2255d20ae88e8c1f5
public/combinat/zabrocki/ncsf_quasi_schur_basis/18447| Stopgaps:
Dependencies: #18415 |
-------------------------------------+-------------------------------------
Comment (by tscrim):
The slowdown is not from the Immaculate basis, but from the Complete basis
to symmetric functions.
{{{
sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: I = NCSF.Immaculate()
sage: C = NCSF.Complete()
sage: x = C(I[4,1,4,6,3,8])
sage: %prun x.to_symmetric_function()
}}}
Current branch
{{{
352005 function calls (351848 primitive calls) in 1.726 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
3340 0.218 0.000 0.854 0.000
algebras_with_basis.py:128(_product_from_combinatorial_algebra_multiply)
3341 0.154 0.000 0.595 0.000
classical.py:94(_element_constructor_)
10024 0.134 0.000 0.268 0.000
partition.py:5064(__contains__)
6683 0.115 0.000 0.311 0.000 partition.py:604(__init__)
6681 0.103 0.000 0.693 0.000
partition.py:548(__classcall_private__)
56381 0.084 0.000 0.084 0.000 {isinstance}
28447 0.083 0.000 0.083 0.000
non_negative_integers.py:94(__contains__)
3341 0.079 0.000 0.748 0.000
ncsf.py:2876(to_symmetric_function_on_generators)
3340 0.073 0.000 0.508 0.000
multiplicative.py:39(_multiply_basis)
6683 0.067 0.000 0.100 0.000 combinat.py:1251(__init__)
3349 0.065 0.000 0.089 0.000
free_module.py:2030(_from_dict)
6683 0.064 0.000 0.574 0.000
partition.py:5045(_element_constructor_)
15894 0.035 0.000 0.050 0.000 partition.py:5096(<genexpr>)
12553 0.032 0.000 0.047 0.000 partition.py:627(<genexpr>)
6683 0.032 0.000 0.032 0.000 partition.py:638(__hash__)
6683 0.031 0.000 0.031 0.000 combinat.py:822(__init__)
16727 0.027 0.000 0.125 0.000 {all}
6690 0.025 0.000 0.025 0.000 free_module.py:36(__init__)
3361 0.024 0.000 0.026 0.000
partition.py:4914(__classcall_private__)
596 0.024 0.000 1.613 0.003 {sage.misc.misc_c.prod}
3340 0.022 0.000 0.877 0.000 magmas.py:927(_mul_parent)
50388 0.021 0.000 0.021 0.000 {len}
2 0.018 0.009 1.655 0.827
{sage.combinat.dict_addition.dict_linear_combination}
3340 0.015 0.000 0.015 0.000 {method 'sort' of 'list'
objects}
3349 0.015 0.000 0.017 0.000 sf.py:883(complete)
7276 0.014 0.000 0.014 0.000 combinat.py:1172(__iter__)
3340 0.014 0.000 0.901 0.000 magmas.py:875(__mul__)
6781/6780 0.013 0.000 0.016 0.000 {hasattr}
30 0.012 0.000 0.012 0.000
dynamic_class.py:324(dynamic_class_internal)
3936 0.010 0.000 0.688 0.000
generic_basis_code.py:1110(<genexpr>)
6680 0.010 0.000 0.010 0.000 combinat.py:1146(__len__)
13361 0.008 0.000 0.008 0.000 {method 'iteritems' of
'dict' objects}
6680 0.008 0.000 0.008 0.000
free_module.py:2084(<genexpr>)
}}}
With 02d585f:
{{{
55438 function calls (55282 primitive calls) in 0.461 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
597 0.087 0.000 0.127 0.000 family.py:852(__init__)
698/697 0.027 0.000 0.031 0.000 {hasattr}
597 0.024 0.000 0.422 0.001
ncsf.py:2815(to_symmetric_function_on_basis)
6680 0.022 0.000 0.022 0.000
non_negative_integers.py:94(__contains__)
598 0.021 0.000 0.032 0.000
free_module.py:1895(_monomial)
2 0.021 0.010 0.394 0.197
{sage.combinat.dict_addition.dict_linear_combination}
3340 0.016 0.000 0.024 0.000 partition.py:5096(<genexpr>)
9531 0.015 0.000 0.015 0.000 {isinstance}
3340 0.015 0.000 0.023 0.000 partition.py:627(<genexpr>)
611 0.012 0.000 0.016 0.000 {sorted}
31 0.012 0.000 0.012 0.000
dynamic_class.py:324(dynamic_class_internal)
598 0.012 0.000 0.051 0.000 partition.py:604(__init__)
598 0.012 0.000 0.050 0.000
partition.py:5064(__contains__)
597 0.011 0.000 0.147 0.000
graded_modules_with_basis.py:42(basis)
597 0.011 0.000 0.122 0.000
partition.py:548(__classcall_private__)
597 0.011 0.000 0.193 0.000 sfa.py:1459(__getitem__)
718 0.008 0.000 0.021 0.000
dynamic_class.py:122(dynamic_class)
1323 0.008 0.000 0.010 0.000 combinat.py:961(__eq__)
598 0.007 0.000 0.010 0.000 combinat.py:1251(__init__)
598 0.007 0.000 0.109 0.000
partition.py:5045(_element_constructor_)
597 0.006 0.000 0.136 0.000 family.py:44(Family)
597 0.005 0.000 0.006 0.000 copy.py:66(copy)
28 0.005 0.000 0.007 0.000 homset.py:546(__init__)
1217 0.004 0.000 0.052 0.000 {all}
597 0.004 0.000 0.361 0.001 morphism.py:384(<genexpr>)
605 0.004 0.000 0.007 0.000
free_module.py:2030(_from_dict)
598 0.004 0.000 0.004 0.000 partition.py:638(__hash__)
605 0.004 0.000 0.006 0.000 sf.py:883(complete)
598 0.003 0.000 0.003 0.000 combinat.py:822(__init__)
28 0.003 0.000 0.019 0.001 homset.py:86(Hom)
605 0.003 0.000 0.003 0.000 free_module.py:36(__init__)
597 0.003 0.000 0.364 0.001
free_module.py:1870(<genexpr>)
21 0.002 0.000 0.026 0.001 morphism.py:159(__init__)
}}}
It seems that going from the Complete basis is faster to be a module
morphism rather than an algebra morphism (which for this, makes sense
because we are just sorting the composition and we don't need to multiply
non-monomial elements).
--
Ticket URL: <http://trac.sagemath.org/ticket/18447#comment:34>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
