#6771: Singular pow is really slow
---------------------------------------+------------------------
Reporter: was | Owner: malb
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.4
Component: commutative algebra | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------------+------------------------
Changes (by rws):
* owner: burcin => malb
* component: calculus => commutative algebra
Old description:
> {{{
> > sage: var("x y z")
> > (x, y, z)
> > sage: a = (x+y+z)**20
> > sage: b = a.expand()
> > sage: %time c = factor(b)
> > CPU times: user 0.14 s, sys: 0.00 s, total: 0.15 s
> > Wall time: 0.15 s
> >
> >
> > 1) it uses pari, right?
>
> NO. Pari has no functionality at all for doing anything nontrivial with
> multivariate polynomials. Do b.factor?? to see the source. Sage tries
> to convert b to a poly over QQ, this works, then it calls SINGULAR to
> factor that. If conversion doesn't work, it falls back to Maxima right
> now.
>
> All the time is actually spent in converting b from Pynac to Singular:
>
> sage: timeit('c = b.polynomial(QQ)')
> 5 loops, best of 3: 149 ms per loop
>
> It is silly that this is slow. I don't know why it is so slow.
>
> Mike Hansen wrote some really beautiful-looking clever code in
>
> sage/symbolic/expression_conversions.py
>
> The code that implements b.polynomial is some of this clever code.
> When I read that code (when refereeing the symbolic switch), I think
> "wow, this is beautiful, it is so simple to read/understand, it is short.
> Wow. I bet this is going to be really slow..." Well, evidently it is
> really slow. Somebody should do some profiling and speed this up -- a
> factor of 100 should be easily obtained.
> }}}
>
> It's the conversion itself not the tree walk:
> {{{
> ncalls tottime percall cumtime percall filename:lineno(function)
> 630 0.033 0.000 0.060 0.000
> expression_conversions.py:1004(symbol)
> 799/1 0.014 0.000 0.111 0.111
> expression_conversions.py:1081(arithmetic)
> }}}
> and so I doubt walking the tree in GiNaC would make a difference.
New description:
{{{
> sage: var("x y z")
> (x, y, z)
> sage: a = (x+y+z)**20
> sage: b = a.expand()
> sage: %time c = factor(b)
> CPU times: user 0.14 s, sys: 0.00 s, total: 0.15 s
> Wall time: 0.15 s
>
>
> 1) it uses pari, right?
NO. Pari has no functionality at all for doing anything nontrivial with
multivariate polynomials. Do b.factor?? to see the source. Sage tries
to convert b to a poly over QQ, this works, then it calls SINGULAR to
factor that. If conversion doesn't work, it falls back to Maxima right
now.
All the time is actually spent in converting b to Singular:
sage: timeit('c = b.polynomial(QQ)')
5 loops, best of 3: 149 ms per loop
It is silly that this is slow. I don't know why it is so slow.
It's the conversion itself not the tree walk:
{{{
ncalls tottime percall cumtime percall filename:lineno(function)
630 0.033 0.000 0.060 0.000
expression_conversions.py:1004(symbol)
799/1 0.014 0.000 0.111 0.111
expression_conversions.py:1081(arithmetic)
}}}
The most time intensive functions (via `sage.misc.gperftools`):
{{{
sage: t=((x+y+z)^400).polynomial(QQ)
267 14.7% 45.4% 267 14.7% _int_free
178 9.8% 56.5% 181 10.0% _int_malloc
128 7.1% 73.0% 128 7.1% mpn_add_n
124 6.8% 6.9% 899 49.6%
p_Minus_mm_Mult_qq__FieldQ_LengthThree_OrdPosNomogPos
117 6.5% 63.1% 178 9.8% __GI___libc_malloc
117 6.5% 79.5% 117 6.5% mpn_copyi
114 6.3% 20.3% 397 21.9% __GI___libc_realloc
80 4.4% 12.4% 529 29.2% _nlMult_aNoImm_OR_bNoImm
66 3.6% 83.1% 68 3.8% __GI___libc_free
}}}
(Originally it was hypothecized to be a Pynac problem)
--
Comment:
This has nothing to do with Pynac which is not called here. The most time
intensive functions (via `sage.misc.gperftools`):
{{{
sage: t=((x+y+z)^400).polynomial(QQ)
267 14.7% 45.4% 267 14.7% _int_free
178 9.8% 56.5% 181 10.0% _int_malloc
128 7.1% 73.0% 128 7.1% mpn_add_n
124 6.8% 6.9% 899 49.6%
p_Minus_mm_Mult_qq__FieldQ_LengthThree_OrdPosNomogPos
117 6.5% 63.1% 178 9.8% __GI___libc_malloc
117 6.5% 79.5% 117 6.5% mpn_copyi
114 6.3% 20.3% 397 21.9% __GI___libc_realloc
80 4.4% 12.4% 529 29.2% _nlMult_aNoImm_OR_bNoImm
66 3.6% 83.1% 68 3.8% __GI___libc_free
}}}
In fact, Pynac is one order of magnitude faster:
{{{
sage: %time t=((x+y+z)^400).expand()
CPU times: user 1.69 s, sys: 21 ms, total: 1.71 s
Wall time: 1.71 s
sage: %time t=((x+y+z)^400).polynomial(QQ)
CPU times: user 15.5 s, sys: 6 ms, total: 15.5 s
Wall time: 15.5 s
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/6771#comment:9>
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.
