Opened 9 years ago

Closed 6 years ago

#14878 closed defect (fixed)

Doctest fix for: very slow taylor expansion for composite functions

Reported by: Frédéric Chapoton Owned by: Burcin Erocal
Priority: major Milestone: sage-7.5
Component: symbolics Keywords: taylor expansion, symbolic function
Cc: Merged in:
Authors: Ralf Stephan Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: ebaf2c4 (Commits, GitHub, GitLab) Commit: ebaf2c4e031c16b836004f47fbbf62c624016bf6
Dependencies: #21827 Stopgaps:

Status badges

Description (last modified by Ralf Stephan)

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.

Change History (22)

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

Summary: very slow taylor epansion for composite functionsvery 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.1sage-6.2

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

Replying to chapoton:

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.2sage-6.3

comment:7 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

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

Milestone: sage-6.4sage-6.7

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

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

New commits:

20163ebtrac #14878 sin for power series, step1

comment:10 Changed 7 years ago by git

Commit: 20163eb42cc3095b6112bb9ff24d129b5ad7c795ed55e282a55ecbe91aede9a2f15322a42b1af84a

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

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

comment:11 Changed 7 years ago by git

Commit: ed55e282a55ecbe91aede9a2f15322a42b1af84a2e093f60af2e54d05970902b1e0e2836425a632a

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

0a0921cMerge branch 'u/chapoton/14878' into 7.1.b0
2e093f6trac #14878 now sin and cos for all power series

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

Branch: u/chapoton/14878
Commit: 2e093f60af2e54d05970902b1e0e2836425a632a

branch transfered to #20017

comment:13 Changed 7 years ago by Ralf Stephan

Report Upstream: N/AReported 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
Description: modified (diff)
Milestone: sage-6.10sage-7.5
Report Upstream: 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
Status: newneeds_review
Summary: very slow taylor expansion for composite functionsDoctest fix for: very slow taylor expansion for composite functions

New commits:

ebaf2c4add 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
Status: needs_reviewpositive_review

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

comment:21 Changed 6 years ago by Ralf Stephan

Authors: Ralf Stephan
Report Upstream: Fixed upstream, in a later stable release.N/A

Thanks too.

comment:22 Changed 6 years ago by Volker Braun

Branch: u/rws/very_slow_taylor_expansion_for_composite_functionsebaf2c4e031c16b836004f47fbbf62c624016bf6
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.