# US 2008/0189345 A1 · Efficient symbolic differentiation using derivative graph factorization > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2008/0189345 A1 - Document ID: US20080189345A1 - Status: Published application - Kind: A1 - Application number: 11/672,475 - Filed: 2007-02-07 - Published: 2008-08-07 - Earliest claimed: 2007-02-07 - Assignees: Microsoft Corporation - Inventors: Brian K. Guenter - Web page: https://patentgrep.com/patent/US20080189345A1 ## CPC - G06F 17/10: Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An efficient symbolic differentiation method and system that automatically computes one or more derivatives of a function using a computing device. A derivative graph is used to graphically represent the derivative of a function. Repeated factorization of the derivative graph yields a factored derivative graph. The derivative is computed by summing the products along all product paths in the factored derivative graph. The efficient symbolic differentiation method and system operates on both single input/single output and multiple input/multiple output functions. For a single input/single output function, the order of the factoring does not matter. However, for a multiple input/multiple output function, the factoring order is such that the factor subgraph appearing most frequently in the derivative graph is factored first. The method and system also use a product pairs priority queue to avoid the re-computing of sub-strings that are common between product paths. ## Claims ### Claim 1 A method for performing symbolic differentiation of a function using a computing device, comprising: representing the function as an expression graph; constructing a derivative graph from the expression graph to graphically represent a derivative of the function; factoring out factor subgraphs from the derivative graph to generate a factored derivative graph; and computing the derivative as a sum of products along all product paths in the factored derivative graph. ### Claim 2 (depends on 1) The method of claim 1, further comprising: determining that at least one node on the derivative graph satisfies the postdominator test or the dominator test; and factoring the derivative graph until no additional factoring can be performed. ### Claim 3 (depends on 1) The method of claim 1, wherein factoring further comprises replacing a factor subgraph with an edge subgraph containing a single edge. ### Claim 4 (depends on 3) The method of claim 3, further comprising replacing each of the factor subgraphs with corresponding edge subgraphs until the factored derivative graph collapses into a single edge. ### Claim 5 (depends on 1) The method of claim 1, wherein the function is a multiple input and multiple output function having n inputs and m outputs, and further comprising: generating nm derivative graphs by taking derivates with respect to each of a plurality of range elements; and finding factor subgraphs where each of the derivative graphs intersect. ### Claim 6 (depends on 5) The method of claim 5, further comprising: counting a frequency in which the factor subgraphs appear in the derivative graphs; ranking each of the factor subgraphs using a priority queue in an order based on the frequency such that a factor subgraph having a highest frequency has a highest ranking; and factoring first a factor subgraph having a highest ranking in the priority queue. ### Claim 7 (depends on 6) The method of claim 6, further comprising updating the ranking of each factor subgraph such that the ranking is changes each time a factor subgraph in the derivative graph due to factorization. ### Claim 8 (depends on 1) The method of claim 1, further comprising: generating intermediate results for each product path in the factored derivative graph; determining sub-products that are common between intermediate results; determining a number of product paths that pass through each of the sub-products; and forming an optimal sub-product having a highest number of product paths that pass through each of the sub-products. ### Claim 9 (depends on 8) The method of claim 8, further comprising: computing a path counts of pairs of edges that occur in sequence along a product path; and determining a highest path count; merging the highest pair count into an edge pair; and inserting the edge pair into product paths of derivative graph containing the edge pair. ### Claim 10 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. ### Claim 11 (depends on 10) The computer-readable medium of claim 10, further comprising defining a product path as a path along the factored derivative graph from the single input to the single output or vice versa. ### Claim 12 (depends on 10) The computer-readable medium of claim 10, further comprising identifying a potential factorization of the derivative graph when two or more products paths pass through a same node en route to a root or a leaf of the derivative graph. ### Claim 13 (depends on 10) The computer-readable medium of claim 10, wherein the postdominator test further comprises: identifying a first node and a second node on the derivative graph; recognizing that the first node is on every product path from the second node to a leaf on the derivative graph; and concluding that the first node satisfies the postdominator test. ### Claim 14 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. ### Claim 15 (depends on 14) The computer-implemented process of claim 14, further comprising: keeping a count of the number of times each of the factor subgraphs appears in the derivative graph; and decrementing the count for a certain factor subgraph whenever during factorization the factor subgraph disappears. ### Claim 16 (depends on 15) The computer-implemented process of claim 15, further comprising updating the count by observing whether a node of a deleted edge is either a factor or a factor base node. ### Claim 17 (depends on 14) The computer-implemented process of claim 14, further comprising: computing a number of product paths that pass through each of a plurality of sub-products; and forming a sub-product having a highest path count. ### Claim 18 (depends on 17) The computer-implemented process of claim 17, further comprising computing path counts of pairs of edges that occur in sequence along the product paths. ### Claim 19 (depends on 18) The computer-implemented process of claim 18, further comprising merging a highest pair count into an edge pair. ### Claim 20 (depends on 19) The computer-implemented process of claim 19, further comprising: inserting the edge pair into all paths of all derivative graphs that contain the edge pair; and continuing the above process until all path in all derivative graphs are one edge long.