[sage-devel] GiNaC as the symbolic manipulation engine in Sage

(this won't get to sage-devel)
1. There are fixes to the general simplifier using hash coding that make
collection and ordering of terms run much faster.
In essence, replacing sorting that probably takes O(n^3) time by O(n) time.
I have provided these, but there are some nuances to integrating these fixes
that other people should look at.

2. The fixes are, to some extent, irrelevant for the following reason:
 If the problem is large and consists of polynomial arithmetic, you should
use rat() form.
If the problem is large and is NOT obviously polynomial arithmetic, you
should make some substitutions and
convert it to polynomial form if at all possible.

My guess is that code that is 1000 times slower than Mathematica will most
likely be made 100, 1000 or even 5000 times faster by the judicious
insertion of rat() somewhere. 

> -----Original Message-----
> From: maxima-bounces at math.utexas.edu 
> [mailto:maxima-bounces at math.utexas.edu] On Behalf Of Robert Dodier
> Sent: Monday, August 11, 2008 7:27 PM
> To: sage-devel
> Cc: maxima at math.utexas.edu
> Subject: Re: [Maxima] [sage-devel] GiNaC as the symbolic 
> manipulation engine in Sage
> 
> William Stein wrote:
> 
> > I have seen a lot of *real* benchmarks involving symbolic calculus
> > when sad users and students come to me and ask why their code
> > is 1000 times slower than Mathematica.  This happened a *few* times
> > today at Sage Days 9 today.  It also comes up in sage-support all
> > the time.  I really need to come up with a large list of 
> specific examples
> > like this, since I'm getting way too confused by benchmarks.
> 
> Yeah. I 'd like to see that list, when you have it.
> 
> In the case of the summation problem mentioned in this thread,
> the central problem is that Maxima's simplification algorithm
> for the result (something of the form (x + y)^2 + (x + y)^4 + ...)
> seems to run in n^2 time where n is the number of terms.
> 
> There is also a trade-off in the summation algorithm:
> in this case it would be faster to generate a list of all the
> terms and then apply "+" to them, but if all the terms are
> numbers, the calculation could be done in constant space
> by adding each term to a running total; the latter is the
> current implementation. Probably the trade-off should go
> the other way; I 'll look at that.
> 
> I'll look at the "+" simplification algorithm to see if I can see
> a way to speed it up. Interested parties may direct
> followups to the Maxima mailing list.
> 
> best
> 
> Robert Dodier
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>