Symbolic computation is slow

[pgdoyle]

I'm having problems doing symbolic computations in Sage. Calls to
rational_simplify() seem to take about .2 seconds each. Working
directly in Maxima is about 100 times faster. Mathematica is
something like 500 times faster.

In Sage, where does the time go? Is there something I can do right
now to speed things up? Is this something that will eventually go
faster?

Cheers,

Peter Doyle
-------------------------
sage: var(x)
x
sage: time sum(((x+sin(i))/x+(x-sin(i))/x).rational_simplify() for i
in xrange(100))
200
CPU time: 5.29 s, Wall time: 39.10 s
sage: time maxima('sum(ratsimp((x+sin(i))/x+(x-sin(i))/x),i,1,100)')
200
CPU time: 0.02 s, Wall time: 0.55 s
sage: time mathematica('Sum[Simplify[(x+Sin[i])/x+(x-Sin[i])/x],{i,
1,100}]')
200
CPU time: 0.00 s, Wall time: 0.09 s
sage: time maxima('sum(ratsimp((x+sin(i))/x+(x-sin(i))/x),i,1,10000)')
20000
CPU time: 0.01 s, Wall time: 30.21 s
sage: time mathematica('Sum[Simplify[(x+Sin[i])/x+(x-Sin[i])/x],{i,
1,10000}]')
20000
CPU time: 0.01 s, Wall time: 2.20 s
sage: time mathematica('Sum[Simplify[(x+Sin[i])/x+(x-Sin[i])/x],{i,
1,100000}]')
200000
CPU time: 0.00 s, Wall time: 70.05 s
sage: time mathematica('Sum[Evaluate[Simplify[(x+Sin[i])/x+(x-Sin[i])/
x]],{i,1,100000}]')
200000
CPU time: 0.00 s, Wall time: 0.03 s

[Mike Hansen]

Hello,

The reason why the symbolic stuff in Sage is slow is that it uses a
psuedo-tty interface to talk to Maxima. There is a lot of overhead
with this due to waiting, synchronization, parsing the string output,
etc. One way to get the symbolic stuff to be faster is to make using
Sympy since it won't have that overhead (even though it is slower than
native maxima at the moment).

--Mike

[Ondrej Certik]

On Dec 27, 9:57 pm, "Mike Hansen" <mhan...@gmail.com> wrote:
> Hello,
>
> The reason why the symbolic stuff in Sage is slow is that it uses a
> psuedo-tty interface to talk to Maxima. There is a lot of overhead
> with this due to waiting, synchronization, parsing the string output,
> etc. One way to get the symbolic stuff to be faster is to make using
> Sympy since it won't have that overhead (even though it is slower than
> native maxima at the moment).

It's indeed 7x faster in SymPy:

In [2]: time sum(((x+sin(i))/x+(x-sin(i))/x).expand() for i in
xrange(100))
CPU times: user 0.54 s, sys: 0.00 s, total: 0.54 s
Wall time: 0.54
Out[2]: 200

than in Sage:

sage: time sum(((x+sin(i))/x+(x-sin(i))/x).rational_simplify() for i
in xrange(100))

CPU times: user 0.60 s, sys: 0.24 s, total: 0.85 s
Wall time: 3.92
200

However, when SymPy is used inside Sage:

sage: from sympy import sympify
sage: x = sympify(x)
sage: time sum(((x+sin(i))/x+(x-sin(i))/x).expand() for i in
xrange(100))
CPU times: user 2.49 s, sys: 0.48 s, total: 2.97 s
Wall time: 6.88
200

It's actually twice slower than Sage+Maxima. Probably some unnecessary
conversions are happening in there.

We also have a project sympycore, as a playground of new ideas, that
we then want to incorporate in SymPy and that one is 23x faster than
Sage:

In [4]: time sum(((x+Sin(i))/x+(x-Sin(i))/x).expand() for i in
xrange(100))
CPU times: user 0.17 s, sys: 0.00 s, total: 0.17 s
Wall time: 0.17
Out[4]: 200


So definitely we are working on improving this, but it will take some
time, before Sage can do this by default.


Ondrej

[William Stein]

On Dec 27, 2007 1:53 PM, pgdoyle <petergr...@gmail.com> wrote:
> I'm having problems doing symbolic computations in Sage. Calls to
> rational_simplify() seem to take about .2 seconds each. Working
> directly in Maxima is about 100 times faster. Mathematica is
> something like 500 times faster.
>
> In Sage, where does the time go? Is there something I can do right
> now to speed things up? Is this something that will eventually go
> faster?
>
> Cheers,
>
> Peter Doyle
> -------------------------
> sage: var(x)
> x
> sage: time sum(((x+sin(i))/x+(x-sin(i))/x).rational_simplify() for i
> in xrange(100))
> 200
> CPU time: 5.29 s, Wall time: 39.10 s
> sage: time maxima('sum(ratsimp((x+sin(i))/x+(x-sin(i))/x),i,1,100)')
> 200
> CPU time: 0.02 s, Wall time: 0.55 s

Those times above are really weird. On my laptop (OSX 10.5.1):

sage: var(x)
x
sage: time sum(((x+sin(i))/x+(x-sin(i))/x).rational_simplify() for i
in xrange(100))
200

Time: CPU 0.97 s, Wall: 3.20 s

sage: time maxima('sum(ratsimp((x+sin(i))/x+(x-sin(i))/x),i,1,100)')
200

CPU time: 0.01 s, Wall time: 0.34 s

Thus it takes 3.2 seconds wall time instead of 39.10 seconds for me.

If you use more specialized algebraic structures in Sage, then the
time directly in Sage comes down a lot (to beat Maxima):

sage: x = RDF['x'].gen()
sage: time sum(((x+math.sin(i))/x+(x-math.sin(i))/x) for i in xrange(100))
200.0*x^200/(1.0*x^200)
CPU time: 0.20 s, Wall time: 0.21 s

Above we make x the indeterminate of the RDF[x], and use the floating
point sin function from Python. But it's not symbolic.

But sympy is still way faster and is symbolic:

sage: from sympy import Symbol, sin
sage: x = Symbol('x')
sage: time sum(((x+sin(i))/x+(x-sin(i))/x).expand() for i in xrange(100))
200
Time: CPU 0.09 s, Wall: 0.09 s

which is why it's a good thing that sympy is the future of symbolic
computation in Sage :-).

And since Sympy comes with Sage, maybe you can use it for
your intended application right now?!

-- William

> sage: time mathematica('Sum[Simplify[(x+Sin[i])/x+(x-Sin[i])/x],{i,
> 1,100}]')
> 200
> CPU time: 0.00 s, Wall time: 0.09 s
> sage: time maxima('sum(ratsimp((x+sin(i))/x+(x-sin(i))/x),i,1,10000)')
> 20000
> CPU time: 0.01 s, Wall time: 30.21 s
> sage: time mathematica('Sum[Simplify[(x+Sin[i])/x+(x-Sin[i])/x],{i,
> 1,10000}]')
> 20000
> CPU time: 0.01 s, Wall time: 2.20 s
> sage: time mathematica('Sum[Simplify[(x+Sin[i])/x+(x-Sin[i])/x],{i,
> 1,100000}]')
> 200000
> CPU time: 0.00 s, Wall time: 70.05 s
> sage: time mathematica('Sum[Evaluate[Simplify[(x+Sin[i])/x+(x-Sin[i])/
> x]],{i,1,100000}]')
> 200000
> CPU time: 0.00 s, Wall time: 0.03 s
> >
>

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[pgdoyle]

> > sage: var(x)
> > x
> > sage: time sum(((x+sin(i))/x+(x-sin(i))/x).rational_simplify() for i
> > in xrange(100))
> > 200
> > CPU time: 5.29 s,  Wall time: 39.10 s
> > sage: time maxima('sum(ratsimp((x+sin(i))/x+(x-sin(i))/x),i,1,100)')
> > 200
> > CPU time: 0.02 s,  Wall time: 0.55 s
>
> Those times above are really weird.  On my laptop (OSX 10.5.1):
>
> sage: var(x)
> x
> sage: time sum(((x+sin(i))/x+(x-sin(i))/x).rational_simplify() for i
> in xrange(100))
> 200
> Time: CPU 0.97 s, Wall: 3.20 s
> sage: time maxima('sum(ratsimp((x+sin(i))/x+(x-sin(i))/x),i,1,100)')
> 200
> CPU time: 0.01 s,  Wall time: 0.34 s
>
> Thus it takes 3.2 seconds wall time instead of 39.10 seconds for me.
>

This was on an old, slow machine, and maybe there is thrashing because
there isn't much RAM.

>
> But sympy is still way faster and is symbolic:
>
> sage: from sympy import Symbol, sin
> sage: x = Symbol('x')
> sage: time sum(((x+sin(i))/x+(x-sin(i))/x).expand() for i in xrange(100))
> 200
> Time: CPU 0.09 s, Wall: 0.09 s
>
> which is why it's a good thing that sympy is the future of symbolic
> computation in Sage :-).
>

This sounds promising.

> And since Sympy comes with Sage, maybe you can use it for
> your intended application right now?!
>

My intended application involves working with matrices, and I it looks
like this isn't going to work with sympy:

sage: from sympy import Symbol

sage: x = Symbol('x')

sage: m=matrix([[x]])
Traceback (most recent call last):
...
AssertionError: <class 'sympy.core.symbol.Symbol'>


Cheers,

Peter Doyle

[Mike Hansen]

Hello,

Sympy provides it's own matrices. As mentioned before, there needs to
be more work done with sympy in Sage so that what you tried does work.
In the meantime, look at the following example:

sage: import sympy
sage: x = sympy.Symbol('x')
sage: m = sympy.Matrix([[1,x],[x,1]])
sage: m
1 x
x 1
sage: m^int(2)
1 + x**2 2*x
2*x 1 + x**2

--Mike

[Ondrej Certik]

On Dec 31, 2007 9:00 PM, Mike Hansen <mha...@gmail.com> wrote:
>
> Hello,
>
> Sympy provides it's own matrices. As mentioned before, there needs to
> be more work done with sympy in Sage so that what you tried does work.
> In the meantime, look at the following example:
>
> sage: import sympy
> sage: x = sympy.Symbol('x')
> sage: m = sympy.Matrix([[1,x],[x,1]])
> sage: m
> 1 x
> x 1
> sage: m^int(2)
> 1 + x**2 2*x
> 2*x 1 + x**2

BTW, we just fixed this ugly output of matrices in sympy, but I didn't
yet update the spkg.

> But sympy is still way faster and is symbolic:
>
> sage: from sympy import Symbol, sin
> sage: x = Symbol('x')
> sage: time sum(((x+sin(i))/x+(x-sin(i))/x).expand() for i in xrange(100))
> 200
> Time: CPU 0.09 s, Wall: 0.09 s
>
> which is why it's a good thing that sympy is the future of symbolic
> computation in Sage :-).

I think those timings are wrong, because sympy uses caching:

sage: from sympy import Symbol, sin
sage: x = Symbol('x')
sage: time sum(((x+sin(i))/x+(x-sin(i))/x).expand() for i in xrange(100))

CPU times: user 0.57 s, sys: 0.00 s, total: 0.57 s
Wall time: 0.57
200

sage: time sum(((x+sin(i))/x+(x-sin(i))/x).expand() for i in xrange(100))

CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s
Wall time: 0.09
200

See my previous email in this thread for more accurate timings.

Anyway, if you find any bugs in SymPy, please report them to sympy, so
that we can fix them.

Ondrej