Hi,
so as promised I ran some timings.
Raw data first
--------------
I first tried
trigsimp_groebner((sin(n*x)/cos(n*x)).expand(trig=True), hints=[tan, n])
This essentially benchmarks groebner basis computation for ideals with
many generators.
In [23]: for n in range(1, 8):
....: t1 = time();
....: trigsimp_groebner((sin(n*x)/cos(n*x)).expand(trig=True),
hints=[tan, n])
....: t2 = time()
....: print n, t2-t1
....:
1 0.132801055908
2 0.379322052002
3 0.864864110947
4 2.28033614159
5 8.45091581345
trigsimp_groebner((sin(n*x)/cos(n*x)).expand(trig=True),
hints=[tan(n*x)])
This essentially benchmarks groebner basis computations for few
generators of high degree:
In [4]: for n in range(1, 40, 5):
t1 = time();
trigsimp_groebner((sin(n*x)/cos(n*x)).expand(trig=True),
hints=[tan(n*x)])
t2 = time()
print n, t2-t1
...:
1 0.136708974838
6 0.371760129929
11 0.539211988449
16 0.942713975906
21 0.935333967209
26 1.61687803268
31 1.85935902596
36 4.20615100861
We see that the number of generators is much more important than their
degree.
New let ex = (4*sin(x)*cos(x) + 12*sin(x) + 5*cos(x)**3 + 21*cos(x)**2 +
23*cos(x) + 15)/(-sin(x)*cos(x)**2 + 2*sin(x)*cos(x) + 15*sin(x) +
7*cos(x)**3 + 31*cos(x)**2 + 37*cos(x) + 21)
I tried
trigsimp_groebner(ex**n)
this essentially benchmarks minsolve_linear_system.
In [5]: for n in range(1, 10):
t1 = time();
trigsimp_groebner(ex**n)
t2 = time()
print n, t2-t1
...:
1 0.51485991478
2 0.627775192261
3 3.56026983261
4 2.81163287163
5 19.9118552208
And the performance is horrible.
We can skip the matroid optimization problem with quick=True. This way
we essentially benchmark the reduced() function.
In [6]: for n in range(1, 10):
t1 = time();
trigsimp_groebner(ex**n, quick=True)
t2 = time()
print n, t2-t1
...:
1 0.265341997147
2 0.314915180206
3 1.57273197174
4 1.78025889397
5 4.90359807014
6 5.49381184578
7 15.6038861275
8 16.8213608265
This is quite a bit more stable. But this is mainly because ex is
choosen in a clever way so that the degree of the optimal result grows
very slowly.
Finally I tried some constant-degree expressions in many variables:
for n in range(1, 10):
t1 = time();
trigsimp_groebner(Add(*[sin(y)**3 for y in symbols('x:%s' % n)]),
quick=True)
t2 = time()
print n, t2-t1
...:
1 0.0841059684753
2 0.208977937698
3 0.836284160614
4 2.26324796677
5 6.3292901516
6 16.6491761208
7 43.1681261063
In [5]: for n in range(1, 10):
t1 = time();
trigsimp_groebner(Add(*[sin(y)**5 for y in symbols('x:%s' % n)]),
quick=True)
t2 = time()
print n, t2-t1
...:
1 0.252753973007
2 2.32168602943
3 39.7612462044
Discussion
-----------
There are various other things one can try.
In general, the algorithm consists of three parts (impacting performance):
1. Compute a groebner basis.
2. Investigate fractions of increasing degree.
3. Possibly optimize the solution.
Suppose the expression we are working with yields N generators, with R
relations among them, and the simplest possible fraction has total degree D.
The efficiency of groebner basis algorithms is very complex. It is, in
general, superexponential, and most strongly influenced by R.
The second steps depends mainly on N and D, because these drive up the
number of monomials in our general fraction. The run time is very
roughly O(N**D) This step involves calling reduced() and solving some
linear systems, in general reduced() seems to be the slowest part here.
The speed of step three depends on the same parameters as step two, but
it slows down *much* more quickly, like O(N**(DN)) or so.
For practical applications, the most important problem currently seems
to be the performance of reduced(), or possibly something around it
involving polynomial representation conversion. I shall try to
investigate this more closely. Before that, I will try to polish my
branch and submit a pull request, since I'm pretty sure the code can
also be improved by others in coming up with more clever heuristics for
ideal generation etc.
Best,
Tom
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To post to this group, send email to sympy@googlegroups.com.
To unsubscribe from this group, send email to
sympy+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sympy?hl=en.
