algorithm and data structure for representing the algebraic structure of derivatives?
ExcellentFeng
Suppose I have a function g(x)=exp(f(x)),
I want to represent the algebraic structure of the Nth derivative of
this function in computer. (N can be a large number, say hundreds...).
I have played with N=10ish, and found the number of terms grows
exponentially.
g1 = g*f1
g2 = g*(f1^2 + f2)
g3 = g*(f1^3 + 3*f1*f2 + f3)
...
where g1, f1 denote the first derivative of g and f respectively. f2,
f3, etc. follow the same notation.
My question is: what's the smartest way to represent the whole
structure/expression in computer, for large N? I am going to put the
whole thing into something like a huge lookup table, so when g200
needs to be computed, I recursively compute f1, f2, f3, f4, and all
the way down, building up something like a tree, until 200.
I am sure there are smart algorithm and data structure in the
literature. Any pointers?
Thanks!
user923005
May I suggest news:sci.math.num-analysis for this sort of problem.
If it really does grow exponentially, g200 will not be computable.
I cannot tell from your expression if the growth really is
exponential, especially since exponential growth is calm very near to
the origin.
With a titanic number of terms, you should also be very concerned
about the accuracy of the answer produced.
It would be a shame to calculate terms for a full week and then get a
random number result.
Fred
What practical use is there for computing the 200th derivative of a
function?
Or even the 20th?
--
Fred K
Ben Bacarisse
<snip>
> Suppose I have a function g(x)=exp(f(x)),
>
> I want to represent the algebraic structure of the Nth derivative of
> this function in computer. (N can be a large number, say hundreds...).
>
> I have played with N=10ish, and found the number of terms grows
> exponentially.
>
> g1 = g*f1
> g2 = g*(f1^2 + f2)
> g3 = g*(f1^3 + 3*f1*f2 + f3)
> ...
>
> where g1, f1 denote the first derivative of g and f respectively. f2,
> f3, etc. follow the same notation.
>
> My question is: what's the smartest way to represent the whole
> structure/expression in computer, for large N?
The trouble is that it is almost always the use you make of the data
that determines the best representation, not the data itself. You
have described the data, but not the use.
To take a glib example, the Nth derivative of g(x) can be represented
simply by the number N (or N and the function f it can't be assumed).
The trouble is you can't do very much with this representation, but
some things (for example taking the derivative) are a piece of cake.
I know I am not helping, but you can help yourself get a better answer
from people who know if you say what you will need to do with this
"thing" once you have it represented.
--
Ben.
Martin Eisenberg
> Suppose I have a function g(x)=exp(f(x)),
>
> I want to represent the algebraic structure of the Nth
> derivative of this function in computer. (N can be a large
> number, say hundreds...).
You can see that in each term of the nth derivative, the factors'
differentiation orders sum to n. That is, the terms are naturally
labeled by unordered partitions of n. For example:
> g1 = g*f1
> g2 = g*(f1^2 + f2)
> g3 = g*(f1^3 + 3*f1*f2 + f3)
(1,1,1) (1,2) (3)
So you might compute g^(N) by enumerating p in part(N), forming the
product of f-derivatives each p indicates, and combining the products
with the coefficients. More formally, we have
h[n] = sum_{p in part(n)} a[n,p] b[n,p]
where b[n,p] = prod_{i=1..size(p)} f^(p[i]).
How then to obtain the a[n,p]? To approach this question, let's
represent an unordered partition as a sorted tuple so that
part(n) = {(n), (1,n-1), (1,1,n-2), (2,n-2), ..., (1,...,1)},
and define size((p[1],...,p[s])) := s.
Next, examining how each derivative of g springs from the last, it is
plain that the sum h[n] := g^(n)/g satisfies
h[0] = 1,
h[n+1] = f' h[n] + h[n]'.
This recurrence actually encodes the ways to generate part(n+1) from
part(n): The first term corresponds to prepending a 1 to each tuple
p in part(n). The second term subsumes all ways to increment a single
entry in each p, as seen from the formula for the derivative of a
product applied to b[n,p].
That observation means we can generate the coefficients for h[n] as
the following pseudocode describes. (Note that you needn't carry the
subscript n in an implementation, it's mainly for exposition.)
a[n,p] := 0, all n,p
a[0,()] := 1
for n=0..N-1 do
for p in part(n) do
for <m,q> in succ(p) do
a[n+1,q] += m a[n,p]
end
end
end.
Here I dealt with the sorted-tuple representation by defining the
successor set of a partition p as comprising pairs <m,q> where m is
the number of ways that q can be made from p, and q is a partition of
the next level made either by prepending a 1 or by incrementing the
last entry in some block of equal entries:
succ(p) := {<1,(1,p)>}
U {<m,q> | i=s or p[i] < p[i+1], i=1..s, s=size(p)}
where
m = |{j | p[j] = p[i]}|,
q = (p[1..i-1], p[i]+1, p[i+1..s]).
Now, to make the pseudocode effective, it remains to pick a storage
strategy for the a[p]. Perhaps a map container does it for you;
perhaps you can give the partitions at each level a running index so
that the coefficients can be in an array, I haven't thought about it.
You might also try switching to a representation of partitions
directly in terms of multiplicities -- avoiding counting to get the m
values, at the cost of more complex logic to making the partitions
themselves.
Martin
--
Never make a shoddy design -- it could sell.
--Karl Lagerfeld