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

[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).

[fchapoton]

Branch: u/chapoton/14878

[fchapoton]

Commit: 20163eb

[fchapoton]

New commits:

20163eb

trac #14878 sin for power series, step1

[sagetrac-git]

Changed commit from 20163eb to ed55e28

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ed55e28

trac #14878 step 2, cos for multi-variable power series

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0a0921c	Merge branch 'u/chapoton/14878' into 7.1.b0
2e093f6	trac #14878 now sin and cos for all power series

[sagetrac-git]

Changed commit from ed55e28 to 2e093f6

[fchapoton]

Changed commit from 2e093f6 to none

[fchapoton]

Changed branch from u/chapoton/14878 to none

[fchapoton]

comment:12

branch transfered to #20017

[rwst]

comment:13

The relevant Pynac ticket is pynac/pynac#116

[rwst]

Upstream: Reported upstream. Developers acknowledge bug.

[rwst]

Changed upstream from Reported upstream. Developers acknowledge bug. to Fixed upstream, in a later stable release.

[rwst]

Dependencies: pynac-0.7.0

[rwst]

Branch: u/rws/very_slow_taylor_expansion_for_composite_functions

[rwst]

New commits:

ebaf2c4

add doctests

[rwst]

Commit: ebaf2c4

[rwst]

Changed dependencies from pynac-0.7.0 to #21827

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:20

ok, looks good to me. Thanks for your work. Please add your name as author.

[rwst]

Author: Ralf Stephan

[rwst]

Changed upstream from Fixed upstream, in a later stable release. to none

[rwst]

comment:21

Thanks too.

[vbraun]

Changed branch from u/rws/very_slow_taylor_expansion_for_composite_functions to ebaf2c4