On Mon, Aug 17, 2009 at 1:14 AM, Ondrej Certik<ond...@certik.cz> wrote:
>
> Hi,
>
> at the scipy 09 conference I am going to compare Sage and sympy
> approaches to factoring (and timings) and longer term approaches, so I
> have a few questions about it, so that I understand things correctly.
> If I do:
>
> 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. This is
now trac #6771:
http://trac.sagemath.org/sage_trac/ticket/6771
> 2) can it be made faster (=virtually instant) using singular? I don't
> mean to call singular manually like this:
>
> sage: R.<x,y,z> = QQ[]
> sage: a = (x+y+z)**20
> sage: time factor(a)
> CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
> Wall time: 0.01 s
> (x + y + z)^20
>
>
> it has to be done fully automatically below the hood.
See my above remarks, which I think completely answer this question.
> 3) if so, will it only work for polynomials, or for any symbolic expressions?
>
> If I do:
>
> sage: var("x y z")
> (x, y, z)
> sage: a = (x+y+sin(z))**20
> sage: b = a.expand()
> sage: %time c = factor(b)
> CPU times: user 0.15 s, sys: 0.01 s, total: 0.16 s
> Wall time: 0.59 s
The current code only works for polynomials. One could make something
that works for any symbolic expression, though how well it works is
another question.
> 4) it uses maxima, right? That's why it is slower, right?
The above did, yes. Here's the code:
try:
from sage.rings.all import QQ
f = self.polynomial(QQ)
w = repr(f.factor())
return symbolic_expression_from_string(w)
except TypeError:
pass
return self.parent()(self._maxima_().factor())
> 5) can it be made faster using singular? I guess by substituting some
> dummy symbol for sin(z) and substituting back.
yes.
> E.g. in the long term, once everything is polished, all factoring will
> be more or less as fast as singular?
Yes. And hopefully in the long term singular's factoring will get way
faster, since I think it is not optimal. It has improved a lot -- two
years ago it really sucked, Joel Mohler very articulately complained,
and the Singular team did a great job improving things in response.
> Or will there be some hidden cost
> in converting the expressions back and forth between symbolics (pynac)
> and singular.
There is a cost right now, which isn't hidden very well. In theory
that cost can be dramatically reduced. The whole conversion could be
written in Cython or C++...
William
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
