Let $g(x) = \exp(f(x))$. Assuming numerical (or symbolic) values of $f(x), f'(x), f''(x), \ldots, f^{(n)}(x)$ are known, is there a way to compute $g'(x), g''(x), \ldots g^{(n)}(x)$ (or even the single value $g^{(n)}(x)$) for large $n$ that is faster than explicitly generating and evaluating the expanded symbolic derivative, a polynomial which has $p(n)$ (partition function) terms?
$\begingroup$
$\endgroup$
3
asked Jul 27, 2010 at 23:56
-
1$\begingroup$ en.wikipedia.org/wiki/… $\endgroup$– Steve HuntsmanCommented Jul 28, 2010 at 0:07
-
2$\begingroup$ For a particular n the relevant polynomial is essentially the cycle index polynomial of S_n: qchu.wordpress.com/2009/06/24/… . So knowing how to do this computation for arbitrary f is essentially equivalent to knowing the cycle index polynomial, which encodes a lot of information. $\endgroup$– Qiaochu YuanCommented Jul 28, 2010 at 0:13
-
$\begingroup$ Thanks, this is the terminology I'm looking for. So I guess the question is: is there a better way than the naive one to evaluate this polynomial (the naive method being to generate the expanded polynomial and evaluate it term by term)? $\endgroup$– Fredrik JohanssonCommented Jul 28, 2010 at 1:18
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
Yes, you can. For example, the normal evaluation for $n=6$ requires 33 multiplications and 10 additions. But by using an optimized straight-line program which takes care of common subexpression elimination, you can reduce that to 17 multiplications, 10 additions and 4 assignments. For $n=8$, the reduction in multiplications goes from 84 down to 37, and at $n=12$, it goes from 397 down to 114.
Note that multiplication by constants (like $10f'(x)$) counts as a multiplication too.
You can experiment with these things by using the codegen package in Maple (especially the functions codegen[optimize] with the tryhard option, as well as codegen[cost]). If there is interest, I can post the details of the computation here.
Unfortunately, at this point, I do not immediately see a pattern in the results, so I am not sure how to automate this and produce optimized versions directly. But the answer to your original question is definitely 'yes'.
answered Sep 8, 2010 at 12:10
-
$\begingroup$ Excellent! This doesn't really solve the problem for arbitrary n, though. $\endgroup$ Commented Sep 9, 2010 at 11:48
-
$\begingroup$ Indeed - and I did mention that in my answer. But I believe that at this point, you're all set for a bit of "experimental mathematics" where you stare at the results for sufficiently many n, see patterns, make conjectures, prove them, repeat. I would even be interested in helping such a project along - I just can't lead it, I've got too many other things already on the go. $\endgroup$ Commented Sep 9, 2010 at 12:25
$\begingroup$
$\endgroup$
I feel that I should post an answer, for the benefit of any potential readers from the future...
For simultaneous computation of the first $n$ derivatives, the problem is really computing the exponential of a power series, and it is a classical result that this can be done in $O(M(n))$ arithmetic operations (which most likely is optimal).
See: Brent and Kung, Fast algorithms for manipulating formal power series, Journal of the ACM, 1978. There are more recent papers reducing the implied constant factors.
I'm still not aware of any result to the effect that the $n$th derivative alone can be computed faster than $O(M(n))$.
answered Jan 24, 2015 at 15:29
$\begingroup$
$\endgroup$
1
Try automatic differentiation, which is exact but not symbolic. See also The Arithmetic of Differentiation by L. B. Rall.
-
1$\begingroup$ I don't see how AD helps here. Rather, AD of nth order requires that the symbolic nth derivatives of atomic functions are already known. $\endgroup$ Commented Jul 28, 2010 at 1:09