commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ajo Fod <ajo....@gmail.com>
Subject [MATH] On computational efficiency in DerivativeStructures
Date Thu, 29 Aug 2013 17:05:39 GMT
Hello,

I wonder if the number of computations required to compute a derivative
structure can be reduced. Say the derivative structure of f to order d=2 is
desired:
f(g1(x1), g2(x2), ... gn(xn)) where x1,x2 ... xn are subsets of variables
that are not necessarily disjoint.

For each gi(xi), O(n^2) variables need to be computed while I only need
[xi]^2 different variables. (Where [xi] stands for the cardinality of the
set xi)

In the extreme case say x1...xn are single variables (sets of cardinality
1):
To compute the derivative structure to order 2 of:
f(sin(x1)+cos(x2)+... tan(xn))
O(n^2) values for each of the n components needs to be computed (or at
least memory allocated for that much):
so that is a total of over O(n^3) values.

If there were a way of computing only derivatives of relevant variables,
each term of f() would require only 2 calculations or a total of 2n
calculations.

So, is there a way to compute the derivative of each component separately
and "join" them together? When the derivative structure is sparse, this
should reduce computation required from O(n^3) to O(n) ... quite a large
saving when n is large.

Any comments on this? ... or errors in this line of though?

Thanks,
Ajo.

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message