Opened 9 years ago

Closed 6 years ago

# Doctest fix for: very slow taylor expansion for composite functions

Reported by: Owned by: Frédéric Chapoton Burcin Erocal major sage-7.5 symbolics taylor expansion, symbolic function Ralf Stephan Frédéric Chapoton N/A ebaf2c4 ebaf2c4e031c16b836004f47fbbf62c624016bf6 #21827

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.

### comment:1 Changed 9 years ago by Frédéric Chapoton

Summary: very slow taylor epansion for composite functions → very slow taylor expansion for composite functions

### comment:2 Changed 9 years ago by Fredrik Johansson

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

### comment:3 Changed 9 years ago by Frédéric Chapoton

Description: modified (diff)

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
```

### comment:4 Changed 9 years ago by For batch modifications

Milestone: sage-6.1 → sage-6.2

### comment:5 in reply to:  description Changed 9 years ago by Marc Mezzarobba

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

### comment:6 Changed 9 years ago by For batch modifications

Milestone: sage-6.2 → sage-6.3

### comment:7 Changed 8 years ago by For batch modifications

Milestone: sage-6.3 → sage-6.4

### comment:8 Changed 8 years ago by Frédéric Chapoton

Milestone: sage-6.4 → sage-6.7

### comment:9 Changed 7 years ago by Frédéric Chapoton

Branch: → u/chapoton/14878 → 20163eb42cc3095b6112bb9ff24d129b5ad7c795 sage-6.7 → sage-6.10

New commits:

 ​20163eb `trac #14878 sin for power series, step1`

### comment:10 Changed 7 years ago by git

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

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

### comment:11 Changed 7 years ago by git

Commit: ed55e282a55ecbe91aede9a2f15322a42b1af84a → 2e093f60af2e54d05970902b1e0e2836425a632a

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`

### comment:12 Changed 7 years ago by Frédéric Chapoton

Branch: u/chapoton/14878 2e093f60af2e54d05970902b1e0e2836425a632a

branch transfered to #20017

### comment:13 Changed 7 years ago by Ralf Stephan

Report Upstream: N/A → Reported upstream. Developers acknowledge bug.

The relevant Pynac ticket is https://github.com/pynac/pynac/issues/116

### comment:14 Changed 6 years ago by Ralf Stephan

Dependencies: → pynac-0.7.0 modified (diff) sage-6.10 → sage-7.5 Reported upstream. Developers acknowledge bug. → Fixed upstream, in a later stable release.

### comment:15 Changed 6 years ago by Ralf Stephan

Description: modified (diff)

### comment:16 Changed 6 years ago by Ralf Stephan

Description: modified (diff)

### comment:17 Changed 6 years ago by Ralf Stephan

Branch: → u/rws/very_slow_taylor_expansion_for_composite_functions

### comment:18 Changed 6 years ago by Ralf Stephan

Commit: → ebaf2c4e031c16b836004f47fbbf62c624016bf6 new → needs_review very slow taylor expansion for composite functions → Doctest fix for: very slow taylor expansion for composite functions

New commits:

 ​ebaf2c4 `add doctests`

### comment:19 Changed 6 years ago by Ralf Stephan

Dependencies: pynac-0.7.0 → #21827

### comment:20 Changed 6 years ago by Frédéric Chapoton

Reviewers: → Frédéric Chapoton needs_review → positive_review