Efficient symbolic differentiation using derivative graph factorization

A computer-readable medium having computer-executable instructions running on a computing device for computing a derivative of a function having a single input and a single output, comprising:

• constructing a derivative graph that graphically represents the derivative of the function, the derivative graph having nodes and edges that connect the nodes such that each edge represent a term;
• determining that at least one node of the derivative graph satisfies the postdominator test or the dominator test;
• generating a factored derivative graph by factoring the derivative graph until no additional factoring can occur;
• and
• computing the derivative as the sum of products along all possible product paths in the factored derivative graph.

A computer-implemented process for computing a derivative of a function having multiple inputs and multiple outputs, comprising:

• expressing the function as an expression graph;
• generating a derivative graph from the expression graph, wherein the derivative graph contains a plurality of nodes and edges that connect the nodes to each other, wherein each of the edges has an associated mathematical term;
• determining that at least one node of the derivative graph satisfies the postdominator test or the dominator test;
• factoring out factor subgraphs from the derivative graph such that a factor subgraph appearing most frequently in the derivative graph is factored first to generate a factored derivative graph;
• and
• computing the derivative by summing the each product of all product paths along the factored derivative graph.