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:  sage7.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: 
Description (last modified by )
Pynac0.7.0 uses Flint to get univariate series expansions. For comparison,
now previously sin(x*sin(x*sin(x*sin(x)))).series(x,8) 5055µ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/
. PrePynac 0.7.0 the tests need 11s vs 0.2s with pynac0.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
Summary:  very slow taylor epansion for composite functions → very slow taylor expansion for composite functions 

comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
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
Milestone:  sage6.1 → sage6.2 

comment:5 Changed 9 years ago by
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) 19992011 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
Milestone:  sage6.2 → sage6.3 

comment:7 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

comment:8 Changed 8 years ago by
Milestone:  sage6.4 → sage6.7 

comment:9 Changed 7 years ago by
Branch:  → u/chapoton/14878 

Commit:  → 20163eb42cc3095b6112bb9ff24d129b5ad7c795 
Milestone:  sage6.7 → sage6.10 
New commits:
20163eb  trac #14878 sin for power series, step1

comment:10 Changed 7 years ago by
Commit:  20163eb42cc3095b6112bb9ff24d129b5ad7c795 → ed55e282a55ecbe91aede9a2f15322a42b1af84a 

Branch pushed to git repo; I updated commit sha1. New commits:
ed55e28  trac #14878 step 2, cos for multivariable power series

comment:11 Changed 7 years ago by
Commit:  ed55e282a55ecbe91aede9a2f15322a42b1af84a → 2e093f60af2e54d05970902b1e0e2836425a632a 

comment:12 Changed 7 years ago by
Branch:  u/chapoton/14878 

Commit:  2e093f60af2e54d05970902b1e0e2836425a632a 
branch transfered to #20017
comment:13 Changed 7 years ago by
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
Dependencies:  → pynac0.7.0 

Description:  modified (diff) 
Milestone:  sage6.10 → sage7.5 
Report Upstream:  Reported upstream. Developers acknowledge bug. → Fixed upstream, in a later stable release. 
comment:15 Changed 6 years ago by
Description:  modified (diff) 

comment:16 Changed 6 years ago by
Description:  modified (diff) 

comment:17 Changed 6 years ago by
Branch:  → u/rws/very_slow_taylor_expansion_for_composite_functions 

comment:18 Changed 6 years ago by
Commit:  → ebaf2c4e031c16b836004f47fbbf62c624016bf6 

Status:  new → needs_review 
Summary:  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
Dependencies:  pynac0.7.0 → #21827 

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

Status:  needs_review → positive_review 
ok, looks good to me. Thanks for your work. Please add your name as author.
comment:21 Changed 6 years ago by
Authors:  → Ralf Stephan 

Report Upstream:  Fixed upstream, in a later stable release. → N/A 
Thanks too.
comment:22 Changed 6 years ago by
Branch:  u/rws/very_slow_taylor_expansion_for_composite_functions → ebaf2c4e031c16b836004f47fbbf62c624016bf6 

Resolution:  → fixed 
Status:  positive_review → closed 
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]]
(usingfmpq_poly_sin_series
in this case).