#6771: speed up pynac --> polynomials conversion, since it is really slow
-------------------------------+------------------------
Reporter: was | Owner: burcin
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.4
Component: calculus | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
-------------------------------+------------------------
Description changed by rws:
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.
> }}}
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 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.
}}}
The direct conversion is not much faster:
{{{
sage: %time c = b.polynomial(QQ)
CPU times: user 105 ms, sys: 8 ms, total: 113 ms
Wall time: 103 ms
sage: R.<x,y,z> = QQ[]
sage: %time _=R(b)
CPU times: user 100 ms, sys: 9 ms, total: 109 ms
Wall time: 99.1 ms
}}}
and so I doubt walking the tree in GiNaC would make a difference. This
conjecture could be tested by fine grained profiling, or simply turning
off any conversion while walking the tree.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/6771#comment:7>
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.
