Doctest fix for: very slow taylor expansion for composite functions

[fchapoton]

Pynac-0.7.0 uses Flint to get univariate series expansions. For comparison,

                                             now     previously
sin(x*sin(x*sin(x*sin(x)))).series(x,8)     50-55µs    13.7s
sin(x*sin(x*sin(x*sin(x)))).series(x,12)      69µs      >1min
sin(x*exp(x)).series(x,100)                  3.7ms     11.3s
sin(x*exp(x)).series(x,500)                  215ms       n/a
(sin(x+x^2)*cos(x+x^2)).series(x,1000)       2.86s       n/a

Extensive tests are added with #21730 under tests/. Pre-Pynac 0.7.0 the tests need 11s vs 0.2s with pynac-0.7.0.

Previous ticket description:

The following

f=sin(x*sin(x*sin(x*sin(x))))
f.series(x,8)

takes something like 30s, which seems a bit too much. Maybe there is some bottleneck somewhere ?
On the other hand,

f.taylor(x,0,8)

is faster, but not lightning fast.

In the same spirit, one could try

sage: x=PowerSeriesRing(QQ,'x').gen()
sage: sin(x)
Traceback (most recent call last):
...
TypeError: cannot coerce arguments: no canonical coercion from Power Series Ring in x over Rational Field to Symbolic Ring

It would be good if one could apply symbolic functions to power series and get power series when possible.

Depends on #21827

Component: symbolics

Keywords: taylor expansion, symbolic function

Author: Ralf Stephan

Branch/Commit: ebaf2c4

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/14878

[fredrik-johansson]

comment:2

Being able to apply functions to power series would be useful.

For anyone looking to implement this, note that flint can now natively evaluate elementary functions over Q[[x]] and (Z/nZ)[[x]] (using fmpq_poly_sin_series in this case).

[fchapoton]

comment:3

some timings:

sage: %timeit f.taylor(x,0,8)
100 loops, best of 3: 6.46 ms per loop
sage: %timeit f.series(x,8)
1 loops, best of 3: 42.1 s per loop

[fchapoton]

Description changed:

--- 
+++ 
@@ -5,6 +5,12 @@
 f.series(x,8)
 ```
 takes something like 30s, which seems a bit too much. Maybe there is some bottleneck somewhere ?
+On the other hand, 
+
+```
+f.taylor(x,0,8)
+```
+is faster, but not lightning fast.
 
 In the same spirit, one could try
 

[mezzarobba]

Replying to @fchapoton:

Maybe there is some bottleneck somewhere ?

GiNaC's series expansion code seems to be designed for very small orders only. It is incredibly inefficient otherwise:

ginsh - GiNaC Interactive Shell (ginac V1.6.2)
  __,  _______  Copyright (C) 1999-2011 Johannes Gutenberg University Mainz,
 (__) *       | Germany.  This is free software with ABSOLUTELY NO WARRANTY.
  ._) i N a C | You are welcome to redistribute it under certain conditions.
<-------------' For details type `warranty;'.

Type ?? for a list of help topics.
> time(series(sin(x*sin(x*sin(x*sin(x)))), x==0, 8));
2.352s                                                                          
> time(series(sin(x*sin(x*sin(x*sin(x)))), x==0, 12));                         
40.104s                                                                         

Judging by the number of calls to gcd/lcm reported by %prun f.series(x==0, k) for successive k, the number of operations in ℚ seems to grow at least exponentially with k, and perhaps like k! (while it should be something like O(k³) in a naive implementation, and essentially linear in a careful one).

I think that's the heart of the problem, and the difference between the timings with sage and with ginsh is pynac overhead (which should of course be minimized, but only costs a constant factor).