#14878: very slow taylor expansion for composite functions
-------------------------------------------------+-------------------------
Reporter: chapoton | Owner: burcin
Type: defect | Status: new
Priority: major | Milestone: sage-6.2
Component: symbolics | Resolution:
Keywords: taylor expansion, symbolic | Merged in:
function | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | Stopgaps:
Dependencies: |
-------------------------------------------------+-------------------------
Comment (by mmezzarobba):
Replying to [ticket:14878 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).
--
Ticket URL: <http://trac.sagemath.org/ticket/14878#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
