# [MATH] On computational efficiency in DerivativeStructures

3 messages
Open this post in threaded view
|

## [MATH] On computational efficiency in DerivativeStructures

 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.