Opened 6 years ago

Closed 3 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: 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) Commit: ebaf2c4e031c16b836004f47fbbf62c624016bf6
Dependencies: #21827 Stopgaps:

Description (last modified by rws)

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 6 years ago by chapoton

  • Summary changed from very slow taylor epansion for composite functions to very slow taylor expansion for composite functions

comment:2 Changed 6 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 6 years ago by 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 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 in reply to: ↑ description Changed 6 years ago by mmezzarobba

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 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.7

comment:9 Changed 4 years ago by chapoton

  • Branch set to u/chapoton/14878
  • Commit set to 20163eb42cc3095b6112bb9ff24d129b5ad7c795
  • Milestone changed from sage-6.7 to sage-6.10

New commits:

20163ebtrac #14878 sin for power series, step1

comment:10 Changed 4 years ago by git

  • Commit changed from 20163eb42cc3095b6112bb9ff24d129b5ad7c795 to ed55e282a55ecbe91aede9a2f15322a42b1af84a

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

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

comment:11 Changed 4 years ago by git

  • Commit changed from ed55e282a55ecbe91aede9a2f15322a42b1af84a to 2e093f60af2e54d05970902b1e0e2836425a632a

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 4 years ago by chapoton

  • Branch u/chapoton/14878 deleted
  • Commit 2e093f60af2e54d05970902b1e0e2836425a632a deleted

branch transfered to #20017

comment:13 Changed 4 years ago by rws

  • 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 3 years ago by rws

  • Dependencies set to pynac-0.7.0
  • Description modified (diff)
  • Milestone changed from sage-6.10 to sage-7.5
  • Report Upstream changed from Reported upstream. Developers acknowledge bug. to Fixed upstream, in a later stable release.

comment:15 Changed 3 years ago by rws

  • Description modified (diff)

comment:16 Changed 3 years ago by rws

  • Description modified (diff)

comment:17 Changed 3 years ago by rws

  • Branch set to u/rws/very_slow_taylor_expansion_for_composite_functions

comment:18 Changed 3 years ago by rws

  • 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:

ebaf2c4add doctests

comment:19 Changed 3 years ago by rws

  • Dependencies changed from pynac-0.7.0 to #21827

comment:20 Changed 3 years ago by chapoton

  • 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 3 years ago by rws

  • Authors set to Ralf Stephan
  • Report Upstream changed from Fixed upstream, in a later stable release. to N/A

Thanks too.

comment:22 Changed 3 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.