Opened 8 years ago
Closed 5 years ago
#14878 closed defect (fixed)
Doctest fix for: very slow taylor expansion for composite functions
Reported by:  chapoton  Owned by:  burcin 

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 8 years ago by
 Summary changed from very slow taylor epansion for composite functions to very slow taylor expansion for composite functions
comment:2 Changed 8 years ago by
comment:3 Changed 8 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 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 in reply to: ↑ description Changed 7 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 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:7 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:8 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.7
comment:9 Changed 6 years ago by
 Branch set to u/chapoton/14878
 Commit set to 20163eb42cc3095b6112bb9ff24d129b5ad7c795
 Milestone changed from sage6.7 to sage6.10
New commits:
20163eb  trac #14878 sin for power series, step1

comment:10 Changed 6 years ago by
 Commit changed from 20163eb42cc3095b6112bb9ff24d129b5ad7c795 to 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 6 years ago by
 Commit changed from ed55e282a55ecbe91aede9a2f15322a42b1af84a to 2e093f60af2e54d05970902b1e0e2836425a632a
comment:12 Changed 5 years ago by
 Branch u/chapoton/14878 deleted
 Commit 2e093f60af2e54d05970902b1e0e2836425a632a deleted
branch transfered to #20017
comment:13 Changed 5 years ago by
 Report Upstream changed from N/A to Reported upstream. Developers acknowledge bug.
The relevant Pynac ticket is https://github.com/pynac/pynac/issues/116
comment:14 Changed 5 years ago by
 Dependencies set to pynac0.7.0
 Description modified (diff)
 Milestone changed from sage6.10 to sage7.5
 Report Upstream changed from Reported upstream. Developers acknowledge bug. to Fixed upstream, in a later stable release.
comment:15 Changed 5 years ago by
 Description modified (diff)
comment:16 Changed 5 years ago by
 Description modified (diff)
comment:17 Changed 5 years ago by
 Branch set to u/rws/very_slow_taylor_expansion_for_composite_functions
comment:18 Changed 5 years ago by
 Commit set to ebaf2c4e031c16b836004f47fbbf62c624016bf6
 Status changed from new to needs_review
 Summary changed from very slow taylor expansion for composite functions to Doctest fix for: very slow taylor expansion for composite functions
New commits:
ebaf2c4  add doctests

comment:19 Changed 5 years ago by
 Dependencies changed from pynac0.7.0 to #21827
comment:20 Changed 5 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, looks good to me. Thanks for your work. Please add your name as author.
comment:21 Changed 5 years ago by
 Report Upstream changed from Fixed upstream, in a later stable release. to N/A
Thanks too.
comment:22 Changed 5 years ago by
 Branch changed from u/rws/very_slow_taylor_expansion_for_composite_functions to ebaf2c4e031c16b836004f47fbbf62c624016bf6
 Resolution set to fixed
 Status changed from positive_review to 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).