#13991: Mitigate speed regressions in symmetric function related code due to
#12313
---------------------------------+------------------------------------------
Reporter: nbruin | Owner: sage-combinat
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.7
Component: combinatorics | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Comment (by nbruin):
Cool! this sort of works:
{{{
sage: from sage.combinat.sf.k_dual import DualkSchurFunctions
sage: Sym = SymmetricFunctions(QQ['t'].fraction_field())
sage: dks4 = DualkSchurFunctions(Sym.kBoundedQuotient(4))
sage: X=dks4[0]+ 2*dks4[1] + 3*dks4[2]
sage: X*X; #takes surprisingly long with #12313 applied
sage: import pdb
sage: def test():
....: pdb.set_trace()
....: print X*X
....:
sage: test()
(Pdb) b Hom
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Symmetric Functions over Fraction Field of
Univariate Polynomial Ring in t over Rational Field in the Hall-Littlewood
Qp basis, None)
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Symmetric Functions over Fraction Field of
Univariate Polynomial Ring in t over Rational Field in the Hall-Littlewood
Qp basis, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(213)Hom()
-> try:
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Symmetric Functions over Fraction Field of
Univariate Polynomial Ring in t over Rational Field in the Hall-Littlewood
Qp basis, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Fraction Field of Univariate Polynomial Ring
in t over Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(213)Hom()
-> try:
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Fraction Field of Univariate Polynomial Ring
in t over Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Univariate Polynomial Ring in t over
Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(213)Hom()
-> try:
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Univariate Polynomial Ring in t over
Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(213)Hom()
-> try:
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
(Pdb) p (X,Y,category)
(Partitions of the integer 0, 4-Bounded Quotient of Symmetric Functions
over Fraction Field of Univariate Polynomial Ring in t over Rational Field
in the 4-bounded Hall-Littlewood P basis, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(213)Hom()
-> try:
(Pdb) p (X,Y,category)
(Partitions of the integer 0, 4-Bounded Quotient of Symmetric Functions
over Fraction Field of Univariate Polynomial Ring in t over Rational Field
in the 4-bounded Hall-Littlewood P basis, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Fraction Field of Univariate Polynomial Ring
in t over Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(213)Hom()
-> try:
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Fraction Field of Univariate Polynomial Ring
in t over Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Univariate Polynomial Ring in t over
Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(213)Hom()
-> try:
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Univariate Polynomial Ring in t over
Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(213)Hom()
-> try:
(Pdb) p (X,Y,category)
(Partitions of the integer 0, Rational Field, None)
(Pdb) c
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
(Pdb) p (X,Y,category)
(Partitions of the integer 1, Symmetric Functions over Fraction Field of
Univariate Polynomial Ring in t over Rational Field in the Hall-Littlewood
Qp basis, None)
(Pdb) bt
/usr/local/sage/5.6rc0/local/bin/sage-ipython(62)<module>()
-> ipy_sage.mainloop(sys_exit=1, banner='')
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/IPython/Shell.py(76)mainloop()
-> self.IP.mainloop(banner)
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/IPython/iplib.py(1762)mainloop()
-> self.interact(banner)
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/IPython/iplib.py(2001)interact()
-> more = self.push(line)
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/IPython/iplib.py(2305)push()
-> more = self.runsource('\n'.join(self.buffer), self.filename)
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/IPython/iplib.py(2231)runsource()
-> if self.runcode(code) == 0:
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/IPython/iplib.py(2260)runcode()
-> exec code_obj in self.user_global_ns, self.user_ns
<ipython console>(1)<module>()
<ipython console>(3)test()
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/algebras.py(202)__mul__()
-> return self._mul_(right)
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/magmas.py(361)_mul_parent()
-> return self.parent().product(self, other)
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/combinat/sf/k_dual.py(791)product()
-> return self( x.lift() * y.lift() )
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/sets_cat.py(839)lift()
-> return self.parent().lift(self)
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/combinat/sf/k_dual.py(706)lift()
-> return kmhlp(self(la)).lift()
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/modules_with_basis.py(1390)__call__()
-> return self.codomain().linear_combination(
(self._on_basis(*(before+(index,)+after)), coeff ) for (index, coeff) in
args[self._position] )
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/combinat/free_module.py(1982)linear_combination()
-> return self._from_dict( dict_linear_combination( ( (
element._monomial_coefficients, coeff ) for element, coeff in
iter_of_elements_coeff ), factor_on_left=factor_on_left ),
remove_zeros=False )
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/combinat/free_module.py(1982)<genexpr>()
-> return self._from_dict( dict_linear_combination( ( (
element._monomial_coefficients, coeff ) for element, coeff in
iter_of_elements_coeff ), factor_on_left=factor_on_left ),
remove_zeros=False )
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/modules_with_basis.py(1390)<genexpr>()
-> return self.codomain().linear_combination(
(self._on_basis(*(before+(index,)+after)), coeff ) for (index, coeff) in
args[self._position] )
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/combinat/sf/k_dual.py(1234)_dks_to_khlp_on_basis()
-> return sum( ks(Qp(x)).coefficient(la) * kHLP(x) for x in
Partitions(Partition(la).size(), max_part = self.k))
/usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/combinat/sf/k_dual.py(1234)<genexpr>()
-> return sum( ks(Qp(x)).coefficient(la) * kHLP(x) for x in
Partitions(Partition(la).size(), max_part = self.k))
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/categories/homset.py(212)Hom()
-> key = (X,Y,category)
}}}
So it seems to me the first problem arises in this statement:
{{{
ks(Qp(x)).coefficient(la) * kHLP(x)
}}}
With
{{{
(Pdb) up
> /usr/local/sage/5.6rc0/local/lib/python2.7/site-
packages/sage/combinat/sf/k_dual.py(1234)<genexpr>()
-> return sum( ks(Qp(x)).coefficient(la) * kHLP(x) for x in
Partitions(Partition(la).size(), max_part = self.k))
(Pdb) p x
[1]
(Pdb) p kHLP
4-Bounded Quotient of Symmetric Functions over Fraction Field of
Univariate Polynomial Ring in t over Rational Field in the 4-bounded Hall-
Littlewood P basis
}}}
I guess it's the `kHLP(x)` part where it has to figure out how to make a
`kHLP` element out of `x`. We have
{{{
(Pdb) p x.parent()
Partitions of the integer 1
}}}
which is obviously a parent that needs to be created again and again!
So my guess is that `Partitions(...)` here should be replaced by something
that is a lot more economical about how to represent what it returns (in
particular, they should have a parent `Partitions of Integers`), in which
case THAT parent can be strongly cached, since it's the index test for the
basis of `kHLP`.
Better yet, the call should just be replaced by `give the basis vector of
`kHLP` indexed by the partition `x`.
The lessons here are interesting for people intending to drive Sage's
category and coercion system to its limits:
- making your parent too specific does not come for free: it means many
have to be created, few remain in use, so most of them have to get
recreated time and again.
- don't rely on the coercion/conversion framework if you already know what
you need.
- creating parents should be considered "expensive". They should not be
created in inner loops. The idea is that parents are heavy-weight so that
their elements can be lightweight. That means that sometimes you have to
let your code change perspective even if mathematically this should not be
necessary (see also why, e.g. fractional ideals in number fields aren't
parents, but how you can turn them into, for instance, a `ZZ`-module,
which is a parent).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13991#comment:10>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
