font=footnotesize,labelfont=bf,labelformat=default,name=Fig.,
textfont=normalfont

# Notes on Computational Graph and
Jacobian Accumulation

Yichong Zhou
<EMAIL_ADDRESS>
(Dec 24, 2020)

###### Abstract

The optimal calculation order of a computational graph can be represented by a
set of algebraic expressions. Computational graph and algebraic expression
both have close relations and significant differences, this paper looks into
these relations and differences, making plain their interconvertibility. By
revealing different types of multiplication relations in algebraic expressions
and their elimination dependencies in line-graph, we establish a theoretical
limit on the efficiency of face elimination.

## 1\. Face Elimination and D* Algorithm

After a sparse computational graph or subgraph is linearized, i.e., all the
derivatives denoted by edges and vertices in the computational graph are
evaluated at a point, there are many elimination techniques to accumulate
derivative values, including vertex elimination, edge elimination and face
elimination.

Naumann states in his paper that all the elimination techniques mentioned
above “are based on the elimination of transitive dependences between
variables in $F$. A variable $v_{j}$ depends transitively on $v_{i}$ via
$v_{k}$ if $i\prec k\prec j$. In general, there is no structural
representation for eliminating such dependences in $G$; that is, it cannot be
expressed by modifying either $V$ or $E$. A richer data structure is required,
namely, a directed variant of the line graph of $G$.” “All intermediate
vertices belong to exactly two directed complete bipartite subgraphs of
$\tilde{G}$. They are minimal in one and maximal in the other. Intermediate
vertices in $G$ are mapped onto complete bipartite subgraphs (or bicliques)
$K_{\nu,\mu}$ of $\tilde{G}$”, He continues to explain, “The elimination of
transitive dependences can be interpreted as the elimination of edges in
$\tilde{G}$. The modification of the dual c-graph is referred to as face
elimination in order to distinguish between edge elimination in $\tilde{G}$
and $G$.” ([7] 2003, p5-8)

Griewank and Walther state in their book that in edge elimination “we are
forced to simultaneously merge them with all their predecessor or successor
edges, respectively. Sometimes we may wish to do that only with one of them.
However, that desire cannot be realized by a simple modification of the
linearized computational graph. Instead we have to consider the so-called
line-graph of the computational graph with a slight extension.” They continue:
“Geometrically, we may interpret the edges of the line-graph as faces of the
extended computational graph. Therefore, we will refer to them as faces.” ([1]
2008, p204)

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$e_{1}$$e_{2}$$e_{3}$$e_{5}$$e_{4}$
(a)

$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$ (b)

Figure 1.1: Line-Graph and Biclique

The transitive dependences Naumann talks about are actually the adjacent edge
paths in computational graph, i.e., one in-going edge and one out-going edge
of a vertex form a in-out vertex path. e.g., $(v_{4},v_{3},v_{1})$ in Fig. 1.1
(a) is an adjacent edge path. As multiple paths could overlap on the same edge
and vertex, elimination of one edge could result in elimination of multiple
paths, e.g., adjacent edge path $(v_{4},v_{3},v_{1})$ and
$(v_{4},v_{3},v_{2})$ overlap on edge $e_{3}$, elimination of $e_{3}$ could
result in elimination of $(v_{4},v_{3},v_{1})$ and $(v_{4},v_{3},v_{2})$. It
seems impossible to eliminate transitive dependences or adjacent edge paths
one by one in computational graph. However, adjacent edges connected by one
vertex in $G$ form a complete bipartite subgraph (or biclique) in $\tilde{G}$.
Since every adjacent edge path in $G$ has an edge in $\tilde{G}$ representing
it, e.g., Fig. 1.1 (b) is the line-graph of computational graph Fig. 1.1 (a),
edge $(e_{3},e_{1})$ in Fig. 1.1 (b) represents the adjacent edge path
$(v_{4},v_{3},v_{1})$ in Fig. 1.1 (a), it can be eliminated in the
corresponding line-graph, i.e., face elimination in $\tilde{G}$ is equivalent
to adjacent edge path elimination in $G$.

In an article uploaded in 2017, Naumann and Utke make a further explanation:
“AD exploits the associativity of the chain rule to compute derivatives on the
basis of the dependency information structurally represented by paths in the
computational graph. The derivative computation can be represented by
elimination steps in the computational graph.” “Face elimination reduces the
granularity of an elimination step to a single multiplication operation.” “We
define the optimal Jacobian accumulation (OJA) under chain rule arithmetic as
a computation of Bauer’s formula with minimal multiplication count.” “Until
now there has been no proof that one can attain the minimum with face
elimination either. Face elimination does not cover all possibilities of
computing Bauer’s formula, particularly the commutativity and distributivity
of the multiplications. We outline a proof showing that there is no exploit of
chain rule arithmetic manipulations in Bauer’s formula that can undercut an
optimal face elimination, thereby establishing that face elimination can
indeed solve OJA.” ([8] p1-2)

As for the rule of face elimination, Naumann described as follows:
For all intermediate faces $(i,j)\in\tilde{E}_{Z}$,
“ (1). If there exists a vertex $k\in\tilde{V}$ such that $P_{k}=P_{i}$ and
$S_{k}=S_{j}$, then set $c_{k}=c_{k}+c_{j}c_{i}$ (absorption); else
$\tilde{V}=\tilde{V}\cup\\{k^{\prime}\\}$ with a new vertex $k^{\prime}$ such
that $P_{k^{\prime}}=P_{i}$ and $S_{k^{\prime}}=S_{j}$ (fillin) and labeled
with $c_{k^{\prime}}=c_{j}c_{i}$.
(2). Remove edge $(i,j)$ from $\tilde{E}$.
(3). Remove $i\in\tilde{V}$ if it is isolated. Otherwise, if there exists a
vertex $i^{\prime}\in\tilde{V}$ such that $P_{i^{\prime}}=P_{i}$ and
$S_{i^{\prime}}=S_{i}$, then set $c_{i}=c_{i}+c_{i^{\prime}}$ (merge); remove
$i^{\prime}$.
(4). Repeat Step (3) for $j\in\tilde{V}$. ”
([7] 2003, p8)

In step (1) of Naumann’s rule, the absorption $c_{k}=c_{k}+c_{j}c_{i}$ means
that we can perform this operation by modifying and reusing $k$ instead of
creating a new vertex. On the principle of reusing vertices, when $|S_{i}|=1$,
i.e. $S_{i}=\\{j\\}$, we can perform fillin operation by $c_{i}=c_{j}c_{i}$
and $S_{i}=S_{j}$; when $|P_{j}|=1$, i.e. $P_{j}=\\{i\\}$, we can perform
fillin operation by $c_{j}=c_{j}c_{i}$ and $P_{j}=P_{i}$;

Griewank and Walther also presented their version of modification rules, they
explained that these modifications will not alter the accumulated values
$a_{ij}$, “but hopefully simplifying their computation”. In addition to the
merge and remove operations similar to those in Naumann’s description they
added the “interior vertex split” operation: “make a copy of any interior
vertex by assigning the same value and the same predecessor or successor set
while splitting the other set, i.e., reattaching some of the incoming or some
of the outgoing edges to the new copy.” They continued to explain: “we can
split and merge until every interior vertex $e$ is simply connected in that it
has exactly one incoming and one outgoing edge connecting it to the vertices
$o_{j}$ and $d_{i}$ for which then $c_{e}=a_{ij}$.” “Applying the
modifications described above, one may generate new directed graphs that are
no longer line-graphs of an underlying computational graph.” ([1] p205)

According to the splitting Griewank and Walther mentioned, in addition to
those presented by Naumann, there are more operations that can be performed in
line-graph: If $P_{k}=P_{i}$ and $S_{k}\subset S_{j}$, we can perform
absorption by $c_{k}=c_{k}+c_{j}c_{i}$, $S_{j}=S_{j}-S_{k}$ without removing
$(i,j)$. If $P_{k}\subset P_{i}$ and $S_{k}=S_{j}$, we can perform absorption
by $c_{k}=c_{k}+c_{j}c_{i}$, $P_{i}=P_{i}-P_{k}$ without removing $(i,j)$. If
$P_{k}=P_{i}$ and $S_{k}\supset S_{j}$, we can perform fillin operation by
$\tilde{V}=\tilde{V}\cup\\{k^{\prime}\\}$, $c_{k^{\prime}}=c_{j}c_{i}+c_{k}$,
$S_{k}=S_{k}-S_{j}$ if $|S_{i}|>1\cap|P_{j}|>1$; $c_{i}=c_{j}c_{i}+c_{k}$,
$S_{k}=S_{k}-S_{j}$, $S_{i}=S_{j}$ if $|S_{i}|=1\cap|P_{j}|\geq 1$;
$c_{j}=c_{j}c_{i}+c_{k}$, $S_{k}=S_{k}-S_{j}$, $P_{j}=P_{i}$ if $|S_{i}|\geq
1\cap|P_{j}|=1$. If $P_{k}\supset P_{i}$ and $S_{k}=S_{j}$, we can perform
fillin operation by $\tilde{V}=\tilde{V}\cup\\{k^{\prime}\\}$,
$c_{k^{\prime}}=c_{j}c_{i}+c_{k}$, $P_{k}=P_{k}-P_{i}$ if
$|S_{i}|>1\cap|P_{j}|>1$; $c_{i}=c_{j}c_{i}+c_{k}$, $P_{k}=P_{k}-P_{i}$,
$S_{i}=S_{j}$ if $|S_{i}|=1\cap|P_{j}|\geq 1$; $c_{j}=c_{j}c_{i}+c_{k}$,
$P_{k}=P_{k}-P_{i}$, $P_{j}=P_{i}$ if $|S_{i}|\geq 1\cap|P_{j}|=1$. If there
exists a vertex $i^{\prime}\in\tilde{V}$ such that $P_{i^{\prime}}\supseteq
P_{i}$ and $S_{i^{\prime}}=S_{i}$, then we can perform merge operation by
$c_{i}=c_{i}+c_{i^{\prime}}$, $P_{i^{\prime}}=P_{i^{\prime}}-P_{i}$; or
$P_{i^{\prime}}=P_{i}$ and $S_{i^{\prime}}\supseteq S_{i}$, then we can
perform merge operation by $c_{i}=c_{i}+c_{i^{\prime}}$,
$S_{i^{\prime}}=S_{i^{\prime}}-S_{i}$.

In an article published in 2002, Griewank and Naumann explain the
disadvantages of face elimination: “it is clear that face elimination offers
an even larger number of choices than edge elimination” “a poor choice of edge
or face elimination sequences might lead to an exponential growth of the
intermediate graph structure and thus the overall cost. In other words the
extra freedom may lead one astray, unless suitable safeguards can be found.”
“If implemented dynamically, it also requires examining and possibly
reconnecting all predecessors of the faces origin and all successors of its
destination. Concerning the ratio between the number of floating point
operations and the number of memory accesses, dynamic face elimination is thus
a true nightmare.” “we may view edge and vertex eliminations as chunkings of
face eliminations to achieve a better ratio between computation and
communication operations.” “in any case we must therefore strive for a static
implementation, where all decisions regarding the elimination sequence and the
necessary memory allocations as well as some of the address and pointer
calculation are performed at compile time. They may then be hardwired into a
code for evaluating the Jacobian $F^{\prime}(x)$ efficiently at many different
arguments $x$”. ([3] 2002, p8-9)

Brian Guenter states in his paper that “D* computes efficient symbolic
derivatives by symbolically executing the expression graph at compile time to
eliminate common subexpressions and by exploiting the special nature of the
graph that represents the derivative of a function.” “factorable subgraphs are
defined by a dominator or postdominator node at a branch in the graph. If a
dominator node $b$ has more than one child, or if a post-dominator node b has
more than one parent, then $b$ is a factor node. If $c$ is dominated by a
factor node $b$ and has more than one parent, or $c$ is postdominated by $b$
and has more than one child, then $c$ is a factor base of $b$. A factor
subgraph, $[b,c]$ consists of a factor node $b$, a factor base $c$ of $b$, and
those nodes on any path from $b$ to $c$.” He then describes a factoring
algorithm to eliminate factor subgraph in the derivative graph and convert it
into subgraph edge, adding that “factorization does not change the value of
the sum of products expression which represents the derivative so factor
subgraphs can be factored in any order”. He says “The solution to the problem
of common factor subgraphs is to count the number of times each factor
subgraph $[i,j]$ appears in the $nm$ derivative graphs. The factor subgraph
which appears most often is factored first. If factor subgraph $[k,l]$
disappears in some derivative graphs as a result of factorization then the
count of $[k,l]$ is decremented. To determine if factorization has eliminated
$[k,l]$ from some derivative graph $f_{ij}$ it is only necessary to count the
children of a dominator node or the parents of a postdominator node. If either
is one the factor subgraph no longer exists. The counts of the $[k,l]$ are
efficiently updated during factorization by observing if either node of a
deleted edge is either a factor or factor base node. Ranking of the $[k,l]$
can be done efficiently with a priority queue.” ([5] 2007, p1-7)

## 2\. Differentiation Graph

We realize that, in $\frac{\mathrm{d}y}{\mathrm{d}x}$, the relation between
$\mathrm{d}y$ and $\mathrm{d}x$ is a partial order
$\mathrm{d}y\geq\mathrm{d}x$. e.g., $y=f(g(x))$, if we write
$\frac{\mathrm{d}f}{\mathrm{d}g}$ and $\frac{\mathrm{d}g}{\mathrm{d}x}$ as
$\mathrm{d}f\to\mathrm{d}g$ and $\mathrm{d}g\to\mathrm{d}x$ respectively, the
transitive relation of partial order between $\mathrm{d}f$ and $\mathrm{d}x$
will be denoted by chain rule.

$\frac{\mathrm{d}f}{\mathrm{d}x}=\,\frac{\mathrm{d}f}{\mathrm{d}g}\frac{\mathrm{d}g}{\mathrm{d}x}\implies\,\textrm{d}f\to\textrm{d}x=\mathrm{d}f\to\mathrm{d}g\to\mathrm{d}x$

$\textrm{d}f\to\textrm{d}x$ means $\textrm{d}f$ depends on $\textrm{d}x$ or
there is a path of dependence from $\textrm{d}f$ to $\textrm{d}x$.
The relation between adjacent arrows in the path is multiplication. To get the
value of $\textrm{d}f\to\textrm{d}x$, we multiply all the derivatives of
adjacent pairs along the path from $\mathrm{d}f$ to $\mathrm{d}x$, i.e.,

$\mathrm{d}f\to\mathrm{d}g_{1}\to\mathrm{d}g_{2}\to\cdots\to\mathrm{d}g_{n}\to\mathrm{d}x\implies\frac{\mathrm{d}f}{\mathrm{d}g_{1}}\frac{\mathrm{d}g_{1}}{\mathrm{d}g_{2}}\cdots\frac{\mathrm{d}g_{n}}{\mathrm{d}x}$

As for the multivariate chain rule, e.g., $y=f(g_{1}(x),g_{2}(x),g_{3}(x))$.
The derivative $\frac{\mathrm{d}f}{\mathrm{d}x}$ would be like this:

$\frac{\mathrm{d}f}{\mathrm{d}x}=\frac{\mathrm{d}f}{\mathrm{d}g_{1}}\frac{\mathrm{d}g_{1}}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{2}}\frac{\mathrm{d}g_{2}}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{3}}\frac{\mathrm{d}g_{2}}{\mathrm{d}x}\implies\frac{\mathrm{d}f}{\mathrm{d}x}\,=\,\mathrm{d}f\begin{cases}\to\mathrm{d}g_{1}\to\mathrm{d}x\\\
\to\mathrm{d}g_{2}\to\mathrm{d}x\\\
\to\mathrm{d}g_{3}\to\mathrm{d}x\end{cases}$

Notice that $\mathrm{d}f$ is divided into $\mathrm{d}g_{1}$, $\mathrm{d}g_{2}$
and $\mathrm{d}g_{3}$ three different paths and we sum up all the products of
different paths in the end. The relation between different paths is addition,
i.e.,

$\mathrm{d}f\begin{cases}\to\mathrm{d}g_{1}\to\mathrm{d}x\\\
\to\mathrm{d}g_{2}\to\mathrm{d}x\\\ \;\vdots\\\
\to\mathrm{d}g_{n}\to\mathrm{d}x\end{cases}\implies\frac{\mathrm{d}f}{\mathrm{d}g_{1}}\frac{\mathrm{d}g_{1}}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{2}}\frac{\mathrm{d}g_{2}}{\mathrm{d}x}+\cdots+\frac{\mathrm{d}f}{\mathrm{d}g_{n}}\frac{\mathrm{d}g_{n}}{\mathrm{d}x}$

Suppose there are intermediate variables $\left[g_{1},g_{2},g_{3}\right]$ and
$h$ between $y$ and $x$, e.g.,
$y=f(g_{1}(h(x)),g_{2}(h(x)),g_{3}(h(x)))$, then

$\mathrm{d}f$$\big{\Downarrow}$$\frac{\mathrm{d}f}{\mathrm{d}x}\,=\,\mathrm{d}f\begin{cases}\to\mathrm{d}g_{1}\to\mathrm{d}h\to\mathrm{d}x\\\
\to\mathrm{d}g_{2}\to\mathrm{d}h\to\mathrm{d}x\\\
\to\mathrm{d}g_{3}\to\mathrm{d}h\to\mathrm{d}x\end{cases}$$\big{\Downarrow}$$\frac{\mathrm{d}f}{\mathrm{d}x}=\frac{\mathrm{d}f}{\mathrm{d}g_{1}}\frac{\mathrm{d}g_{1}}{\mathrm{d}h}\frac{\mathrm{d}h}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{2}}\frac{\mathrm{d}g_{2}}{\mathrm{d}h}\frac{\mathrm{d}h}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{3}}\frac{\mathrm{d}g_{3}}{\mathrm{d}h}\frac{\mathrm{d}h}{\mathrm{d}x}$$\mathrm{d}g_{1}$$\mathrm{d}g_{2}$$\mathrm{d}g_{3}$$\mathrm{d}h$$\mathrm{d}h$$\mathrm{d}h$$\mathrm{d}x$$\mathrm{d}x$$\mathrm{d}x$

Figure 2.1: The transformation of differentiation expression

We notice that the above structure forms a rooted tree hierarchy.

In practice, instead of seeing $h$ in different branches as different
subexpressions with the same structure, computing
$\frac{\mathrm{d}h}{\mathrm{d}x}$ and multiplying them by the rest derivatives
in each branch respectively, we would like to factor out the common factor,
compute and multiply by it once for all:

$\frac{\mathrm{d}f}{\mathrm{d}g_{1}}\frac{\mathrm{d}g_{1}}{\mathrm{d}h}\frac{\mathrm{d}h}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{2}}\frac{\mathrm{d}g_{2}}{\mathrm{d}h}\frac{\mathrm{d}h}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{3}}\frac{\mathrm{d}g_{3}}{\mathrm{d}h}\frac{\mathrm{d}h}{\mathrm{d}x}\implies\left(\frac{\mathrm{d}f}{\mathrm{d}g_{1}}\frac{\mathrm{d}g_{1}}{\mathrm{d}h}+\frac{\mathrm{d}f}{\mathrm{d}g_{2}}\frac{\mathrm{d}g_{2}}{\mathrm{d}h}+\frac{\mathrm{d}f}{\mathrm{d}g_{3}}\frac{\mathrm{d}g_{3}}{\mathrm{d}h}\right)\frac{\mathrm{d}h}{\mathrm{d}x}$

Similar to the above factorization, when we factor out the common factor
$\frac{\mathrm{d}h}{\mathrm{d}x}$, we merge the $\mathrm{d}h$ in the graph.

$\mathrm{d}f$$\mathrm{d}g_{1}$$\mathrm{d}g_{2}$$\mathrm{d}g_{3}$$\mathrm{d}h$$\mathrm{d}h$$\mathrm{d}h$$\mathrm{d}x$$\mathrm{d}x$$\mathrm{d}x$$\xRightarrow{\;\frac{\mathrm{d}h}{\mathrm{d}x}\,\;}$$\mathrm{d}f$$\mathrm{d}g_{1}$$\mathrm{d}g_{2}$$\mathrm{d}g_{3}$$\mathrm{d}h$$\mathrm{d}x$

Figure 2.2:

Note that we not only merged all the $\mathrm{d}h$ nodes, but also all the
$\mathrm{d}x$ nodes and the edges between $\mathrm{d}h$ and $\mathrm{d}x$.

The same rule also applies to all the leaf nodes of same variable because
$\frac{\mathrm{d}x}{\mathrm{d}x}=1$.

$\frac{\mathrm{d}f}{\mathrm{d}g_{1}}\frac{\mathrm{d}g_{1}}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{2}}\frac{\mathrm{d}g_{2}}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{3}}\frac{\mathrm{d}g_{2}}{\mathrm{d}x}\implies\left(\frac{\mathrm{d}f}{\mathrm{d}g_{1}}\frac{\mathrm{d}g_{1}}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{2}}\frac{\mathrm{d}g_{2}}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{3}}\frac{\mathrm{d}g_{2}}{\mathrm{d}x}\right)\frac{\mathrm{d}x}{\mathrm{d}x}\implies\left(\frac{\mathrm{d}f}{\mathrm{d}g_{1}}\frac{\mathrm{d}g_{1}}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{2}}\frac{\mathrm{d}g_{2}}{\mathrm{d}x}+\frac{\mathrm{d}f}{\mathrm{d}g_{3}}\frac{\mathrm{d}g_{2}}{\mathrm{d}x}\right)$$\mathrm{d}f$$\mathrm{d}g_{1}$$\mathrm{d}g_{2}$$\mathrm{d}g_{3}$$\mathrm{d}x$$\mathrm{d}x$$\mathrm{d}x$$\xRightarrow[\frac{\mathrm{d}x}{\mathrm{d}x}\;]{\;\,(\;)\,\,\;}$$\mathrm{d}f$$\mathrm{d}g_{1}$$\mathrm{d}g_{2}$$\mathrm{d}g_{3}$$\mathrm{d}x$$\xRightarrow[\,]{\;\,(\;)\,\,\;}$$\mathrm{d}f$$\mathrm{d}g_{1}$$\mathrm{d}g_{2}$$\mathrm{d}g_{3}$$\mathrm{d}x$$\big{\Downarrow}$$\big{\Downarrow}$$\big{\Downarrow}$

Figure 2.3:

Notice that we removed the $\frac{\mathrm{d}x}{\mathrm{d}x}$ self loop in the
end. The parentheses ‘()’ operator, it sees the inside differentiation
expression as a whole and evaluate it before any adjacent outside operation.
Because we see $x$ as the same variable during the process of factoring out
the common factor, naturally it merges all the $\mathrm{d}x$ nodes to
evaluate.

We notice that there is close correspondence between differentiation graph and
differentiation expression which can be converted to each other. Although
differentiation graph and differentiation expression basically are the same
thing in different form, there are some differences between them. The most
obvious one is the terminal variable. In algebraic differentiation expression,
we use the same symbol in different position to denote they are the same,
whereas in differentiation graph, the terminal variable can be in different
positions, e.g., the trees in Fig. 2.2 and Fig. 2.3, they can also be in the
same position, e.g., the DAG’s in Fig. 2.2 and Fig. 2.3.

Note how we arrived at the rooted DAG in Fig. 2.2, we see the rooted tree as
an intermediate graph, just like how we manipulate the function expression:
first construct the tree hierarchy, then factor out the common factor by
merging vertices. The rooted tree is more similar to the algebraic expression
in terms of using same variable in different position. e.g., the trees in Fig.
2.2 and Fig. 2.3 have the exactly same structures as the corresponding
algebraic expression.

So what does $\mathrm{d}y\to\mathrm{d}x$ mean? In fact, we can further
simplify the notation by removing ‘$\mathrm{d}$’: $y\to x$. The arrow $\to$
denotes that variable $y$ depends on variable $x$, and we take the derivative
of $y$ with respect to $x$.Therefore,

$\mathrm{d}f$$\mathrm{d}g_{1}$$\mathrm{d}g_{2}$$\mathrm{d}g_{3}$$\mathrm{d}h$$\mathrm{d}x$
(a)

$\xRightarrow{\quad}$

$f$$g_{1}$$g_{2}$$g_{3}$$h$$x$$\frac{\partial f}{\partial
g_{1}}$$\frac{\partial f}{\partial g_{2}}$$\frac{\partial f}{\partial
g_{3}}$$\frac{\mathrm{d}g_{1}}{\mathrm{d}h}$$\frac{\mathrm{d}g_{2}}{\mathrm{d}h}$$\frac{\mathrm{d}g_{3}}{\mathrm{d}h}$$\frac{\mathrm{d}h}{\mathrm{d}x}$
(b)

$\xRightarrow{\quad}$

$f$$g_{1}$$g_{2}$$g_{3}$$h$$x$ (c)

Figure 2.4: Remove ‘$\mathrm{d}$’

We find that the trace of multi-path chain rule is the trace of dependence in
the function expression. Therefore a differentiation graph is also a
dependence graph of function expressions. For differentiation graph, if we
define the direction of edges in paths as vertical, the direction of aligning
sibling paths is horizontal, according to multi-path chain rule, between edges
in the vertical direction there are multiplication operators, between sibling
paths aligned in the horizontal direction there are addition operators.
However, we cannot compute the root value or intermediate value of function
expression using its dependence graph, as there is no operator in dependence
graph.

Note that if we reverse the direction of all the edges in Fig. 2.4 (c), it
becomes a computational graph. Computational graph is more like a generalized
term, which means it is not limited to the computation of derivatives.
Differentiation graph is computational graph, just like we say differentiation
expression is algebraic expression. As Parr and Howard have mentioned in their
paper([9],2018), the opposite arrow direction denotes the direction of data
flow. In the diagrams of following sections, we will still use the direction
of dependence as the default direction.

## 3\. Notations and Terminology

Let $G=(V,E)$ be a differentiation graph, $v_{i}\in V\ni v_{j}\cap v_{i}\prec
v_{j}$. We use $P_{v_{j}\to v_{i}}$ to denote the set of all the paths from
vertex $v_{j}$ to $v_{i}$ and $p_{v_{j}\to v_{i}}(\in P_{v_{j}\to v_{i}})$ to
denote a path in $P_{v_{j}\to v_{i}}$. $|P_{v_{j}\to v_{i}}|$ is the number of
paths in $P_{v_{j}\to v_{i}}$, $|p_{v_{j}\to v_{i}}|$ is the length of path
$p_{v_{j}\to v_{i}}$, i.e., the number of edges in the path; Then the formula
of multi-path chain rule or Bauer’s formula can be rewritten as:

$\frac{\partial v_{y}}{\partial v_{x}}=\sum_{p_{j}\in\mathrm{P}_{v_{y}\to
v_{x}}}\prod_{e_{i}\in p_{j}}e_{i}$

We use $e_{i}$ to denote the $i$th edge in $E$, and $e_{i}^{-}$ and
$e_{i}^{+}$ to denote the source node and destination node of directed edge
$e_{i}$ respectively. We also use $\langle j,i\rangle$ or $\langle
v_{j},v_{i}\rangle$ to denote the directed edge from vertex $v_{j}$ to
$v_{i}$.

We use $P_{e_{j}\to e_{i}}$ to denote the set of all the paths from edge
$e_{j}$ to $e_{i}$. Apparently, $P_{e_{j}\to e_{i}}\equiv P_{e_{j}^{+}\to
e_{i}^{-}}$. We use $v_{i}^{-}$ and $v_{i}^{+}$ to denote the incoming edges
and outgoing edges of intermediate vertex $v_{i}$ respectively. Therefore the
set of all adjacent edge paths between the incoming edges and outgoing edges
of $v_{i}$ is $P_{v_{i}}\equiv P_{v_{i}^{-}\to v_{i}^{+}}$. $\forall p_{k}\in
P_{v_{i}},|p_{k}|=2$. We use $v_{i}^{--}$ or $v_{i}^{=}$ to denote all the
predecessors of $v_{i}$, and $v_{i}^{++}$ or $v_{i}^{\\#}$ to denote all the
successors of $v_{i}$. Let $V^{\prime}\subseteq V$, then $V^{\prime=}$ is the
set of all the predecessors of vertices in $V^{\prime}$, $V^{\prime\\#}$ is
the set of all the successors of vertices in $V^{\prime}$.

Let $Y$,$Z$,$X$ be the roots, intermediates and terminals respectively, $Y\cup
Z\cup X=V$. Then $P_{Y\to X}$ is the set of all the paths from roots
$\mathrm{Y}$ to terminals $X$. We use $Y^{+}$ to denote all the outgoing edges
from $Y$, $Y^{\\#}$ to denote all the successors of roots, $X^{-}$ to denote
all the incoming edges to $X$, $X^{=}$ to denote all the predecessors of
terminals. $Y^{-}=\emptyset$, $Y^{=}=\emptyset$, $X^{+}=\emptyset$,
$X^{\\#}=\emptyset$. $\forall v_{i}\in V$: if $v_{i}^{-}=\emptyset\cup
v_{i}^{=}=\emptyset$, then $v_{i}\in Y$; if $v_{i}^{+}=\emptyset\cup
v_{i}^{\\#}=\emptyset$, then $v_{i}\in X$;

We use $\mathrm{D}^{-}(v_{i})$ to denote the in-degree of $v_{i}$, i.e., the
number of incoming edges of $v_{i}$, $\mathrm{D}^{+}(v_{i})$ to denote the
out-degree of $v_{i}$, i.e., the number of outgoing edges of $v_{i}$. $\forall
x_{i}\in X,\mathrm{D}^{+}(x_{i})=0$, $\forall y_{j}\in
Y,\mathrm{D}^{-}(y_{j})=0$. $\forall v_{i}\in V,\mathrm{D}^{-}(v_{i})\geq
0,\mathrm{D}^{+}(v_{i})\geq 0$. We use $\mathrm{D}_{r}^{-}(v_{i})$ to denote
the r-degree of $v_{i}$, i.e., the number of root vertices that have at least
one path to $v_{i}$, and $\mathrm{D}_{t}^{+}(v_{i})$ to denote the t-degree of
$v_{i}$, i.e., the number of terminal vertices to which $v_{i}$ has at least
one path. We use $X_{i}$ to denote the set of terminals to which $v_{i}$ has
at least one path, $Y_{i}$ to denote the set of roots that have at least one
path to $v_{i}$. Note that $X_{i}$ and $Y_{i}$ are the concepts of index
domain and index range mentioned in [1] (P147).
$\mathrm{D}_{r}^{-}(v_{i})=|Y_{i}|$, $\mathrm{D}_{t}^{+}(v_{i})=|X_{i}|$.

Notice that there could be more than one path going through one edge. We use
$\mathrm{O}_{P}(e_{k})$ to denote the overlapping degree of an edge $e_{k}\in
E$ in a set of paths $P$, i.e., the number of paths in $P$ going through edge
$e_{k}$. Therefore, $\forall v_{i}\in Z$,

$\mathrm{O}_{P_{v_{i}}}(e_{k})=\begin{cases}\mathrm{D}^{+}(v_{i})&\quad(e_{k}\in
v_{i}^{-})\\\ \mathrm{D}^{-}(v_{i})&\quad(e_{k}\in v_{i}^{+})\end{cases}$

$\forall e_{k}\in E,\mathrm{O}_{P}(e_{k})\geq 0$.

######  Definition 3.1.

In a differentiation graph $G=(V,E)$, if there are at least two separate paths
between vertex $v_{i}$ and $v_{j}$ that do not share any intermediate vertex
at the same graph location, and all the intermediate vertices in $P_{v_{i}\to
v_{j}}$ have no outgoing edge to or incoming edge from vertices that are not
in $P_{v_{i}\to v_{j}}$, then all the vertices(including $v_{i}$ and $v_{j}$)
and edges in all those paths from $v_{i}$ to $v_{j}$ form an block $b\langle
v_{i},v_{j}\rangle$. $v_{i}$ is the source of $b\langle v_{i},v_{j}\rangle$,
$v_{j}$ is the sink of $b\langle v_{i},v_{j}\rangle$.

If there is a block between $v_{i}$ and $v_{j}$, it is a differentiation graph
of $\frac{\mathrm{d}v_{i}}{\mathrm{d}v_{j}}$.

######  Definition 3.2.

Assume that there are two different vertices $v_{i}$ and $v_{j}$ in
differentiation graph $G=(V,E)$. A path $p_{v_{i}\to v_{j}}$ is a direct chain
or direct simple chain $e^{\prime}\langle v_{i},v_{j}\rangle$ if it has at
least 1 intermediate vertex and the in-degree and out-degree of every
intermediate vertex in $p_{v_{i}\to v_{j}}$ are both 1. If after every block
whose intermediate vertices do not include $v_{i}$ or $v_{j}$ is replaced by a
substitute edge in $G$, path $p_{v_{i}\to v_{j}}$ is a direct simple chain
that contains at least 1 substitute edge, then all the non-substitute edges
and all the vertices in $p_{v_{i}\to v_{j}}$ and all the vertices and edges in
the corresponding blocks of those substitute edges in $p_{v_{i}\to v_{j}}$
form an indirect chain $c\langle v_{i},v_{j}\rangle$. Both direct chain and
indirect chain are called chain. If all the corresponding blocks of those
substitute edges in $p_{v_{i}\to v_{j}}$ are simple blocks, then $c\langle
v_{i},v_{j}\rangle$ is an indirect simple chain $e^{\prime}\langle
v_{i},v_{j}\rangle$. Both direct simple chain and indirect simple chain are
called simple chain. If a chain $c\langle v_{i},v_{j}\rangle$ is not an simple
chain, then it is a complex chain. $v_{i}$ is the source of $c\langle
v_{i},v_{j}\rangle$ and $e^{\prime}\langle v_{i},v_{j}\rangle$, $v_{j}$ is the
sink of $c\langle v_{i},v_{j}\rangle$ and $e^{\prime}\langle
v_{i},v_{j}\rangle$.

Note that an edge could be a path of length 1, but here in our definition it
is not a chain, and an indirect chain has more than one path.

######  Definition 3.3.

In a differentiation graph $G=(V,E)$, if every outgoing edge of vertex $v_{i}$
belongs to a simple chain to $v_{j}$ or connects to $v_{j}$, and there are at
least 2 outgoing edge of $v_{i}$ are not in the same simple chain, then all
the vertices(including $v_{i}$ and $v_{j}$) and edges in all those paths from
$v_{i}$ to $v_{j}$ form an simple block $e\langle v_{i},v_{j}\rangle$. $v_{i}$
is the source of $e\langle v_{i},v_{j}\rangle$, $v_{j}$ is the sink of
$e\langle v_{i},v_{j}\rangle$. If all the simple chains in $e\langle
v_{i},v_{j}\rangle$ are direct simple chains, then $e\langle
v_{i},v_{j}\rangle$ is a direct simple block, otherwise it is an indirect
simple block. If a block $b\langle v_{i},v_{j}\rangle$ is not an simple block,
then it is a complex block.

######  Definition 3.4.

In a differentiation graph $G=(V,E)$, all the root vertices are in the same
first level of depth, and all the terminal vertices are in the same last level
of depth. The depth level of an intermediate vertex is the length of the
longest path of all the paths from root vertices to that vertex. We use
$L(v_{i})$ to denote the depth level of vertex $v_{i}$. If vertex $v_{i}$ has
an directed edge $e$ connected to vertex $v_{j}$ and $L(v_{j})-L(v_{i})>1$,
then $e$ is a cross-level edge. We use $L(Y)$ to denote the first level of
depth, $L(X)$ to denote the last level of depth, and $L(G)$ to denote the
depth of $G$. $L(Y)=0$, $L(G)=L(X)$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$e_{1}$$e_{2}$$e_{5}$$e_{3}$$e_{4}$ (a)

$v_{1}$$v_{1}^{\prime}$$v_{2}$$v_{3}$$v_{4}$$e_{1}$$e_{2}$$1$$e_{5}$$e_{3}$$e_{4}$
(b)

$v_{1}$$v_{4}$$v_{2}$$v_{3}$$v_{4}$$e_{1}$$e_{2}$$e_{5}$$1$$e_{3}$$e_{4}$ (c)

Figure 3.1: Cross-level edge segmentation

We can segment a cross-level edge by filling the positions of depth levels
crossed by it with vertices derived from its head or tail vertex, turning it
into a direct simple chain. e.g., Fig. 3.1 (b) or (c) is the segmentation
result of cross-level edge $\langle v_{1},v_{4}\rangle$ in Fig. 3.1 (a). In a
differentiation graph in which all the cross-level edges are segmented, every
two adjacent depth levels form a bipartite subgraph or local Jacobian. Note
that the calculation of $1\cdot e_{5}$ in $(e_{1}e_{3}+1\cdot
e_{5}+e_{2}e_{4})$ is unnecessary, just like the calculation of zero entries
in local Jacobian multiplication.

We denote the set of all vertices in depth level $l$ by $V^{l}$, e.g.,
$Y=V^{0}$, $X=V^{h}$, where $h$ is the depth level of terminals. Let $V^{a}$,
$V^{b}$ and $V^{c}$($a<b<c$) be the sets of vertices in different depth
levels, then for $v_{i}\in V^{b}$, the set of vertices in $V^{c}$ to which
$v_{i}$ has at least one path is $V^{c}_{i}$ or $X^{c}_{i}$, the set of
vertices in $V^{a}$ that have at least one path to $v_{i}$ is $V^{a}_{i}$ or
$Y^{a}_{i}$, where $X_{i}=V^{h}_{i}=X^{h}_{i}$, $Y_{i}=V^{0}_{i}=Y^{0}_{i}$.

We use $J^{i}_{k}$ to denote the Jacobian between depth level $i$ and $k$,
e.g., the global Jacobian is $J^{0}_{L(x)}$. However, local Jacobians are not
limited to two different depth levels. We use $J\langle S_{1}|S_{2}\rangle$ to
denote the Jacobian between two sets of vertices, e.g., $J\langle Y|X\rangle$
is the global Jacobian. We use $J\langle v_{a},v_{b}|v_{c},v_{d}\rangle$ to
denote the local Jacobian between $v_{a},v_{b}$ and $v_{c},v_{d}$, or
$J\langle v_{i}|v_{i}^{\\#}\rangle$ to denote the local Jacobian between
$v_{i}$ and $v_{i}^{\\#}$.

######  Definition 3.5.

Let $G^{\prime}=(U,V,E^{\prime})$ be a bipartite graph or subgraph with
directed edges from $U$ to $V$, after we remove all the directions of directed
edges in $E^{\prime}$, it becomes an undirected graph $G=(V,E)$. If $\exists
v_{i}\in G$, $\forall v_{j}\in G\cap v_{j}\neq v_{i},P_{v_{i}\to
v_{j}}\neq\emptyset$, then $G^{\prime}$ is an undivided bipartite graph or
subgraph.

## 4\. Factorization and Conversion

$v_{1}$$v_{2}$$(1,1)$$v_{3}$$(1,1)$$v_{4}$$(1,1)$$v_{5}$$(1,1)$$v_{6}$$(1,1)$$v_{7}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$
(a)

$v_{1}$$v_{2}$$(1,2)$$v_{3}$$(1,2)$$v_{4}$$(1,1)$$v_{5}$$(2,2)$$v_{6}$$(1,1)$$v_{7}$$(2,1)$$v_{8}$$(2,1)$$v_{9}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{12}$
(b)

$v_{1}$$v_{2}$$v_{2}$$v_{3}$$v_{3}$$v_{4}$$v_{4}$$v_{4}$$v_{4}$$v_{5}$$v_{5}$$v_{6}$$v_{6}$$v_{7}$
(c)

Figure 4.1: Simple Block and Complex Block

The conversion between differentiation graph and algebraic expression is
obvious when the graph is simple. e.g., in Fig. 4.1 (a) there are two simple
blocks $e\langle v_{1},v_{4}\rangle$ and $e\langle v_{4},v_{7}\rangle$ chained
together, we can immediately write down its algebraic expression:

$\frac{\mathrm{d}v_{1}}{\mathrm{d}v_{7}}=(e_{1}e_{3}+e_{2}e_{4})(e_{5}e_{7}+e_{6}e_{8})$
(4.1)

where the edge label $e$ denotes the derivative of its source node with
respect to its destination node, e.g., $e_{1}=\frac{\partial v_{1}}{\partial
v_{2}}$. We notice that a simple block in differentiation graph can be
converted to a subexpression block with parenthesis in algebraic expression.

However, it is difficult to get an algebraic expression in Fig. 4.1 (b) at one
glance, because it is a complex block. Differentiation graph is more flexible
when it comes to the same intermediate variables(vertices) or
derivatives(edges), it can always merge them, whereas in a single algebraic
expression, due to its limitation of expressivity, there is no direct
representation or corresponding counterpart of complex block.

One solution for converting a complex differentiation graph to an algebraic
expression is to transform it into a simple differentiation graph with simple
chains and simple blocks, which can be converted to algebraic expression
directly. e.g., Fig. 4.1 (c) is a direct simple block that lists all paths
from root to terminal in Fig. 4.1 (a). Its algebraic expression would be like
this:

$\frac{\mathrm{d}v_{1}}{\mathrm{d}v_{7}}=\left(e_{1}e_{3}e_{5}e_{7}+e_{1}e_{3}e_{6}e_{8}+e_{2}e_{4}e_{5}e_{7}+e_{2}e_{4}e_{6}e_{8}\right)$
(4.2)

But there is a difference between the result algebraic expressions. Note that
it takes 12 fma’s to compute Eq. 4.2 while only 5 fma’s for Eq. 4.1.

There are two ways to transform Fig. 4.1 (b). One way is that first transform
it to a direct simple block that lists all the paths from root to terminal,
then merge these vertices and edges again, making sure only simple blocks or
simple chains are generated. The other way is to break down the overly merged
graph into a more convertible one that has no complex blocks. e.g., Fig. 4.2
demonstrates how we factorize Fig. 4.1 (b).

$v_{1}$$v_{2}$$(2,1)$$v_{3}$$(2,1)$$v_{4}$$(1,1)$$v_{5}$$(2,1)$$v_{6}$$(1,1)$$v_{7}$$(1,1)$$v_{7}$$(1,1)$$v_{8}$$(1,1)$$v_{8}$$(1,1)$$v_{9}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{12}$$e_{11}$$e_{12}$
(a)

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{7}$$v_{7}$$v_{8}$$v_{9}$$v_{6}$$v_{5}$$v_{7}$$v_{8}$$v_{8}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{6}$$e_{5}$$e_{7}$$e_{8}$$e_{9}$$e_{11}$$e_{11}$$e_{12}$$e_{10}$$e_{8}$$e_{9}$$e_{11}$$e_{12}$$e_{12}$
(b)

$v_{1}$$v_{2}$$(1,1)$$v_{3}$$(1,1)$$v_{2}$$(1,1)$$v_{3}$$(1,1)$$v_{4}$$(1,1)$$v_{5}$$(1,1)$$v_{6}$$(1,1)$$v_{7}$$(1,1)$$v_{8}$$(1,1)$$v_{9}$$e_{1}$$e_{2}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{12}$
(c)

$v_{9}$$v_{7}$$v_{8}$$v_{4}$$v_{5}$$v_{2}$$v_{2}$$v_{3}$$v_{1}$$v_{6}$$v_{5}$$v_{2}$$v_{3}$$v_{3}$$e_{11}$$e_{12}$$e_{7}$$e_{8}$$e_{10}$$e_{9}$$e_{3}$$e_{4}$$e_{5}$$e_{1}$$e_{1}$$e_{2}$$e_{6}$$e_{4}$$e_{5}$$e_{1}$$e_{2}$$e_{2}$
(d)

Figure 4.2: Complex Block Factorization

There are two methods to factorize a complex block: one is forward
factorization, the other is backward factorization.

To apply backward factorization, we first compute the in-degree of every
intermediate vertex in the block, treating every simple block whose
intermediate vertices do not include the vertex being computed as an edge.
e.g., in Fig. 4.1 (a), the in-degree of vertex $v_{4}$ is $1$. Then, from
bottom to top, we search for vertices whose in-degrees are greater than 1,
split from behind the outgoing edges, reducing the overlapping degrees of
outgoing edges to 1. e.g., in Fig. 4.1 (b), $v_{7}$ and $v_{8}$ are the
predecessors of sink $v_{9}$, their in-degrees are both 2, i.e.,
$O_{P_{v_{7}}}(e_{11})=2$ and $O_{P_{v_{8}}}(e_{12})=2$, which means there are
2 paths overlapped on $e_{11}$ and $e_{12}$ respectively, we split from behind
$e_{11}$ and $e_{12}$, by creating another duplicated $v_{7}$ and $v_{8}$,
$e_{11}$ and $e_{12}$ in locations that are different from the original one,
connecting $e_{8}$ and $e_{9}$ to the new $v_{7}$ and new $v_{8}$
respectively, as shown in Fig. 4.2 (a). After that, we adjust the in-degrees
of vertices and continue to search for next target vertex from among the
predecessor vertices of current position, e.g., the in-degree of $v_{5}$ in
Fig. 4.2 (a) is 2. Since $e\langle v_{5},v_{9}\rangle$ is a simple block, we
regard it as one edge, split it just like how we split $e_{11}$ and $e_{12}$
in the previous step, as shown in Fig. 4.2 (b).

Forward factorization is basically the same as backward factorization except
in the opposite direction. Instead of tracking in-degrees of intermediate
vertices, searching for target vertices from bottom up and splitting from
behind an edge, it tracks out-degrees, searches for target vertices from top
down and splits from the head of an edge. Fig. 4.2 (c) and (d) illustrate the
process of forward factorization.

We can quickly convert a simple block to an algebraic expression. The
algebraic expression of Fig. 4.2 (b) is:

$\frac{\mathrm{d}v_{1}}{\mathrm{d}v_{7}}=e_{1}(e_{3}e_{7}e_{11}+e_{4}(e_{8}e_{11}+e_{9}e_{12}))+e_{2}(e_{6}e_{10}e_{12}+e_{5}(e_{8}e_{11}+e_{9}e_{12}))$
(4.3)

The algebraic expression of Fig. 4.2 (d) is:

$\frac{\mathrm{d}v_{1}}{\mathrm{d}v_{7}}=(e_{1}e_{3}e_{7}+(e_{1}e_{4}+e_{2}e_{5})e_{8})e_{11}+(e_{2}e_{6}e_{10}+(e_{1}e_{4}+e_{2}e_{5})e_{9})e_{12}$
(4.4)

Note that in Eq. 4.3 and Eq. 4.4, the same intermediate variable or
subexpression $(e_{8}e_{11}+e_{9}e_{12})$ and $(e_{1}e_{4}+e_{2}e_{5})$ cannot
be factored out despite they can be merged in the graph. In practice, we would
like to use some intermediate variables to offset the limitation of a single
algebraic expression. e.g., let $s_{1}=e_{8}e_{11}+e_{9}e_{12}$, Eq. 4.3
becomes:

$\frac{\mathrm{d}v_{1}}{\mathrm{d}v_{7}}=e_{1}(e_{3}e_{7}e_{11}+e_{4}s_{1})+e_{2}(e_{6}e_{10}e_{12}+e_{5}s_{1})$
(4.5)

If we put $(e_{8}e_{11}+e_{9}e_{12})$ under the Eq. 4.5, and draw two directed
edges from the bottom of $s_{1}$’s in different locations to the top of it,
denoting ‘$=$’ or reference, it becomes a DAG. We notice that multiple
algebraic expressions connected by intermediate variables is effectively a DAG
of references. During the process of complex block factorization, in order to
take advantage of the reference structure of multiple algebraic expressions,
for every simple block that splits like an edge, we can create a new reference
edge representing it, and replace it with that edge before splitting. e.g., in
Fig. 4.3, a new edge $s_{1}$ is created to replace $e\langle
v_{5},v_{9}\rangle$.

$v_{1}$$v_{2}$$(2,1)$$v_{3}$$(2,1)$$v_{4}$$(1,1)$$v_{5}$$(2,1)$$v_{6}$$(1,1)$$v_{7}$$(1,1)$$v_{7}$$(1,1)$$v_{8}$$(1,1)$$v_{8}$$(1,1)$$v_{9}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{12}$$e_{11}$$e_{12}$
(a)

$v_{1}$$v_{2}$$(2,1)$$v_{3}$$(2,1)$$v_{4}$$(1,1)$$v_{5}$$(2,1)$$v_{6}$$(1,1)$$v_{7}$$(1,1)$$v_{8}$$(1,1)$$v_{9}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$s_{1}$$e_{10}$$e_{11}$$e_{12}$
(b)

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{5}$$v_{7}$$v_{8}$$v_{9}$$v_{6}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{6}$$e_{5}$$e_{7}$$s_{1}$$e_{11}$$e_{10}$$s_{1}$$e_{12}$
(c)

Figure 4.3: Factorization with Reference

Differentiation graph is path-oriented, edges and vertices are the carrier of
paths, multiple paths could overlap on the same edges and vertices. In a
direct simple chain, all the edges and vertices form only one path, therefore
elimination of path is equivalent to elimination of corresponding edges and
vertices. We notice that simple chains and simple blocks could be nested
structures like algebraic expressions. In an optimized arithmetic expression,
the optimal calculation order is from inside out, so are the simple blocks and
simple chains. When the most inner direct simple chains and direct simple
blocks are eliminated and replaced by shortcut edges, the second most inner
indirect simple chains and indirect simple blocks become direct simple chains
and direct simple blocks. We can repeat this all the way to the outermost
simple chains and simple blocks. Thus, for the simple blocks and simple
chains, elimination of paths is equivalent to elimination of corresponding
edges and vertices as long as it follows the optimal calculation order. Notice
that in Fig. 4.3 (a), $e\langle v_{5},v_{9}\rangle$ and
$(e_{8}e_{11}+e_{9}e_{12})$ are equivalent, $(e_{8}e_{11}+e_{9}e_{12})$ is the
algebraic form, $e\langle v_{5},v_{9}\rangle$ is the graph form. We can easily
convert a simple block or a simple chain to its corresponding algebraic form,
and then deduce it back again from the algebraic expression we have, they are
interconvertible. It is worth noting that the commutativity of multiplication
relation in algebraic expression, e.g., $e_{i}e_{j}$ and $e_{j}e_{i}$, makes
sense while in differentiation graph makes no sense because $e_{i}\succ e_{j}$
or $e_{i}^{-}\succ e_{i}^{+}=e_{j}^{-}\succ e_{j}^{+}$. Therefore, the
precondition of their interconvertibility is to impose noncommutativity
restriction of multiplication relation on the algebraic expressions converted
from differentiation graph.

$\underbrace{\left[e_{1},e_{2}\right]}_{A}\times\underbrace{\left[\begin{matrix}e_{3}&e_{4}&0\\\
0&e_{5}&e_{6}\end{matrix}\right]}_{B}\times\underbrace{\left[\begin{matrix}e_{7}&0\\\
e_{8}&e_{9}\\\
0&e_{10}\end{matrix}\right]}_{C}\times\underbrace{\left[\begin{matrix}e_{11}\\\
e_{12}\end{matrix}\right]}_{D}$ (4.6)

Notice that we can convert Fig. 4.1 (b) to the form of local Jacobians, as
shown in Eq. 4.6. If we use $(AB)$ to denote the matrix product of $A$ and
$B$, then $(AB)CD$ is the Fig. 4.2 (c), $((AB)C)D$ is the Fig. 4.2 (d),
$AB(CD)$ is the Fig. 4.2 (a), $A(B(CD))$ is the Fig. 4.2 (b). The accumulation
process of $ABCD$ is the factorization process of differentiation graph in
Fig. 4.1 (b). If we accumulate it from left to right, i.e. $(((AB)C)D)$, the
result is Eq. 4.4; from right to left, i.e. $(A(B(CD)))$, the result is Eq.
4.3. Similar to the reference edge in Fig. 4.3, we can also use reference
variables to replace the entries in $(AB)$. It is worth noting that there are
more than just two accumulation orders we discussed above, we can accumulate
local Jacobians from both sides or from the middle, e.g., $((AB)(CD))$ or
$((A(BC))D)$, which means we can also factorize complex blocks from both sides
or from the middle. Different accumulation orders result in different
algebraic expressions with different structures, our goal is to find an
algebraic expression that requires less fma’s to compute. Note that local
Jacobian accumulation merges or eliminates depth levels through matrix
multiplications. Despite it can automatically factorize complex blocks by
treating every entry of the result local Jacobian as an independent simple
block or simple chain and packing their accumulations into one atomic
operation, it ignores the optimal calculation order in the simple chains and
simple blocks, which means it is up to us to find a better accumulation order.
e.g., in Fig. 4.1 (a), we prefer $(J^{0}_{1}J^{1}_{2})(J^{2}_{3}J^{3}_{4})$ to
$J^{0}_{1}(J^{1}_{2}J^{2}_{3})J^{3}_{4}$, because the latter splits $v_{4}$
into 4 vertices, resulting in Fig. 4.1 (c), which requires more fma’s to
compute.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$v_{14}$$v_{15}$$v_{16}$$v_{17}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{12}$$e_{13}$$e_{14}$$e_{15}$$e_{16}$$e_{17}$$e_{18}$
(a)

$v_{1}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{10}$$v_{11}$$v_{14}$$v_{15}$$v_{16}$$v_{17}$$s_{1}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$s_{2}$$e_{15}$$e_{16}$$e_{17}$$e_{18}$
(b)

Figure 4.4: Conflicting depth accumulation order

When accumulating local Jacobians of different depth levels, sometime
different subgraphs may have conflicting optimal accumulation orders, e.g., in
Fig. 4.4 (a), the optimal accumulation order for the left subgraph is
$(J^{0}_{1}J^{1}_{2})(J^{2}_{3}J^{3}_{4})J^{4}_{5}$, while for the right
subgraph is $J^{0}_{1}(J^{1}_{2}J^{2}_{3})(J^{3}_{4}J^{4}_{5})$. Although
depth local Jacobian multiplication can be performed separately in unrelated
sub-graphs that span the same depth levels, local Jacobians are not limited to
two different depth levels, we can also apply non-depth local Jacobian
accumulation, e.g., the result of $J\langle
v_{1},v_{11}|v_{2},v_{3},v_{12},v_{13}\rangle\times J\langle
v_{2},v_{3},v_{12},v_{13}|v_{4},v_{14}\rangle=J\langle
v_{1},v_{11}|v_{4},v_{14}\rangle$ is Fig. 4.4 (b), where
$s_{1}=e_{1}e_{3}+e_{2}e_{4}$ and $s_{2}=e_{11}e_{13}+e_{12}e_{14}$. In fact,
we can first eliminate all the simple chains and simple blocks in a
differentiation graph using reference edge, and eliminate depth levels by
performing depth local Jacobian multiplication when accumulating layered dense
graph or subgraph.

$y_{1}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{12}$$x_{9}$
(a)

$y_{1}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{11}$$e_{12}$$e_{12}$$x_{9}$
(b)

$y_{1}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$s_{1}$$e_{7}$$e_{10}$$e_{11}$$e_{12}$$x_{9}$
(c)

$y_{1}$$e_{1}$$e_{2}$$e_{4}$$e_{5}$$e_{3}e_{7}$$e_{8}$$e_{9}$$e_{6}e_{10}$$e_{11}$$e_{12}$$x_{9}$
(d)

$y_{1}$$e_{1}$$e_{2}$$e_{4}$$e_{5}$$e_{3}e_{7}e_{11}$$e_{9}$$e_{6}e_{10}$$e_{8}e_{11}$$e_{12}$$x_{9}$
(e)

$y_{1}$$e_{1}$$e_{2}$$e_{4}$$e_{5}$$e_{3}e_{7}e_{11}$$e_{6}e_{10}e_{12}$$s_{1}$$x_{9}$
(f)

Figure 4.5: Chain-Block Elimination in the Line-Graph

Note that we can perform face elimination in the line-graph in the same way
how we factorize the differentiation graph, splitting vertices explicitly,
then eliminating edges, as shown in Fig. 4.5 (a) (b) (c). We can also perform
face elimination using the rules presented by Naumann, splitting vertices
implicitly, as shown in Fig. 4.5 (d) (e) (f). The first way is more similar to
the corresponding algebraic expression, while the second way costs less when
implementing the process in a program, because it creates less new vertices.

## 5\. Multi-Root or Multi-Terminal

So far we have only considered the situation of $(|Y|=1)\cap(|X|=1)$. When
$|Y|>1$ or $|X|>1$, multiple blocks or chains are intertwined together, the
subgraph of every root-terminal pair is a chain or block. Then, how do we
factorize a graph with multiple root vertices or terminal vertices? As
Griewank and Walther state in their book that “…a large number of additive
terms that have many common multiplicative subexpressions. Hence, the
challenge is now to organize the computation such that a large number of these
subexpressions is identified and reused not only for a single pair $(j,i)$ but
across all nonzero partials $a_{ij}$.” ([1] 2008, p196) We need to identify
the common sub-chains or sub-blocks nested in root-terminal chains or blocks,
and replace them with reference edges.

The purpose of multiple blocks or chains being intertwined together is to
merge the same common sub-chains or sub-blocks. If the outmost blocks or
chains have no nested common sub-chains or sub-blocks, there is no need to put
them together to compute, they can be easily separated from each other. Just
like local Jacobian accumulation sees every entry of the result local Jacobian
independently, another solution is to simply list or completely split all the
sub-graphs of root-terminal pairs from the differentiation graph as the
entries of root-terminal Jacobian, since they do not share any common sub-
chain or sub-block that needs be computed first. e.g., we can list all the
root-terminal pairs in Fig. 1.1 (a). In other words, if we know the optimal
common sub-chain or sub-block combination set, we can compute them separately.
The upper bound is that we ignore the common sub-chains or sub-blocks,
separating root-terminal pairs directly and optimizing them individually.

We notice that different combination set of root-terminal chains or blocks may
have different set of common sub-chains or sub-blocks. Let
$A=\\{(v_{i},v_{j})|v_{i}\in Y,v_{j}\in X\\}$, $B=\\{S|S\subseteq A\\}$,
$C=\\{S|S\subseteq B\\}$, then $|B|=2^{|A|}=2^{|X|\cdot|Y|}$,
$|C|=2^{|B|}=2^{2^{|X|\cdot|Y|}}$. When $|X|$ and $|Y|$ increase, $|B|$
increases exponentially and $|C|$ increases doubly exponentially, it becomes
extremely difficult to conduct a brute-force search for a optimal combination
that requires minimum number of fma’s to compute the root-terminal Jacobian.
However, the combinations in $B$ are not equally important, we need to narrow
down the searching space, e.g., find the largest common sub-chains or sub-
blocks overlapped by most root-terminal pairs, where ‘largest’ means largest
number of fma’s needed to compute it. Another problem is that when a solution
is found, how do we prove that it is optimal? What if there is another
solution that requires less fma’s to calculate? It is hard to verify if the
solution is optimal, especially when $|X|\cdot|Y|$ is large. What we can do is
to find a solution that requires as less fma’s as possible.

Note that the optimal dynamic value accumulation in linearized differentiation
graph is not the optimal calculation order. If the cost of searching for an
optimal calculation order exceeds the calculation cost saved by the optimal
calculation order, we would rather not do it. However, for a static symbolic
differentiation graph that calculates a lot of different inputs, the optimal
calculation order matters.

$v_{0}$$v_{-1}$$v_{-2}$$v_{-3}$$v_{1}$$(2,4)$$v_{2}$$(3,4)$$v_{3}$$(3,4)$$v_{4}$$(3,3)$$v_{5}$$(4,4)$$v_{6}$$(3,3)$$v_{7}$$(4,3)$$v_{8}$$(4,3)$$v_{9}$$(4,2)$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$e_{0}$$e_{17}$$e_{18}$$e_{19}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{12}$$e_{13}$$e_{14}$$e_{15}$$e_{16}$
(a)

$y_{2}$$y_{4}$$y_{3}$$y_{1}$$e_{18}$$e_{0}$$e_{17}$$e_{19}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{12}$$e_{15}$$e_{13}$$e_{14}$$e_{16}$$x_{3}$$x_{1}$$x_{2}$$x_{4}$
(b)

Figure 5.1: Multi-root and Multi-terminal Differentiation Graph and Line Graph

For example, Fig. 5.1 (a) is a multi-root and multi-terminal differentiation
graph. We notice that if we ignore all the vertices and edges not in
$P_{v_{-2}\to v_{12}}$, i.e., all the vertices and edges that are irrelevant
to the calculation of $\frac{\partial v_{-2}}{\partial v_{12}}$, then all the
relevant vertices and edges in $P_{v_{-2}\to v_{12}}$ form an indirect simple
chain $e^{\prime}\langle v_{-2},v_{12}\rangle$. We can quickly write down its
algebraic form: $e_{18}(e_{3}e_{7}+e_{4}e_{8})e_{15}$. However after finishing
the calculation or conversion, we find ourselves in an awkward situation: it
cannot be eliminated directly, because $\forall e_{k}\in P_{v_{-2}\to
v_{12}},\mathrm{O}_{P_{Y\to X}}(e_{k})>1$. Similarly, in its corresponding
line-graph Fig. 5.1 (b), it cannot be eliminated directly either, because
$\forall e_{k}\in P_{y_{2}\to
x_{3}},\mathrm{O}_{P_{\tilde{Y}\to\tilde{X}}}(e_{k})>1$.

$v_{0}$$v_{-1}$$v_{-2}$$v_{-3}$$v_{-4}$$v_{14}$$(1,1)$$v_{1}$$(3,4)$$v_{2}$$(3,4)$$v_{3}$$(3,4)$$v_{4}$$(3,3)$$v_{5}$$(4,4)$$v_{6}$$(3,3)$$v_{7}$$(4,3)$$v_{8}$$(4,3)$$v_{9}$$(4,2)$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$e_{0}$$e_{17}$$e_{18}$$e_{20}$$e_{19}$$e_{21}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$$e_{10}$$e_{11}$$e_{12}$$e_{13}$$e_{14}$$e_{15}$$e_{16}$$e_{22}$
(a)

$v_{0}$$v_{-1}$$v_{-2}$$v_{-3}$$v_{-4}$$v_{1}$$(3,4)$$v_{2}$$(3,4)$$v_{3}$$(3,4)$$v_{5}$$(4,4)$$v_{7}$$(4,3)$$v_{8}$$(4,3)$$v_{9}$$(4,2)$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$e_{0}$$e_{17}$$e_{18}$$e_{20}$$e_{19}$$s_{3}$$e_{1}$$e_{2}$$s_{1}$$e_{4}$$e_{5}$$s_{2}$$e_{8}$$e_{9}$$e_{11}$$e_{12}$$e_{13}$$e_{14}$$e_{15}$$e_{16}$
(b)

$v_{0}$$v_{-1}$$v_{-2}$$v_{-3}$$v_{1}$$(3,4)$$v_{2}$$(3,4)$$v_{3}$$(3,4)$$v_{5}$$(4,4)$$v_{7}$$(4,3)$$v_{8}$$(4,3)$$v_{9}$$(4,2)$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$e_{0}$$e_{17}$$e_{18}$$e_{20}$$e_{19}$$e_{1}$$e_{2}$$s_{1}$$e_{4}$$e_{5}$$s_{2}$$e_{8}$$e_{9}$$e_{11}$$e_{12}$$e_{13}$$e_{14}$$e_{15}$$e_{16}$
(c)

$v_{0}$$v_{-1}$$v_{-2}$$v_{1}$$(3,4)$$v_{2}$$(3,4)$$v_{3}$$(3,4)$$v_{5}$$(3,4)$$v_{7}$$(3,3)$$v_{8}$$(3,3)$$v_{9}$$(3,2)$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$e_{0}$$e_{17}$$e_{20}$$e_{1}$$e_{2}$$s_{1}$$e_{4}$$e_{5}$$s_{2}$$e_{8}$$e_{9}$$e_{11}$$e_{12}$$e_{13}$$e_{14}$$e_{15}$$e_{16}$
(d)

$v_{-2}$$v_{-3}$$v_{2}$$(1,4)$$v_{3}$$(1,4)$$v_{5}$$(2,4)$$v_{7}$$(2,3)$$v_{8}$$(2,3)$$v_{9}$$(2,2)$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$s_{1}$$e_{4}$$e_{5}$$s_{2}$$e_{8}$$e_{9}$$e_{11}$$e_{12}$
(e)

$v_{0}$$v_{-1}$$v_{-2}$$v_{1}$$(3,4)$$v_{7}$$(3,3)$$v_{8}$$(3,3)$$v_{9}$$(3,2)$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$e_{0}$$e_{15}$$s_{8}$$s_{9}$$e_{11}$$e_{12}$
(f)

$v_{-2}$$v_{-3}$$v_{2}$$(1,2)$$v_{3}$$(1,2)$$v_{5}$$(2,2)$$v_{7}$$(2,1)$$v_{8}$$(2,1)$$v_{12}$$v_{13}$$s_{1}$$e_{4}$$e_{5}$$s_{2}$$e_{8}$$e_{9}$
(g)

$v_{-2}$$v_{-3}$$v_{2}$$(1,2)$$v_{3}$$(1,2)$$v_{5}$$(2,2)$$v_{7}$$(2,2)$$v_{8}$$(2,2)$$v_{9}$$(2,2)$$v_{10}$$v_{11}$$s_{1}$$e_{4}$$e_{5}$$s_{2}$$e_{8}$$e_{9}$$e_{11}$$e_{12}$
(h)

$v_{-2}$$v_{-3}$$v_{9}$$(2,2)$$v_{10}$$v_{11}$ (i)

Figure 5.2: Multi-Roots or Multi-Terminals Factorization

Our strategy of finding common sub-chains and sub-blocks:
1\. If there are simple chains or simple blocks, replace them with reference
edges. e.g., after replacing all the simple chains in Fig. 5.2 (a), it becomes
Fig. 5.2 (b).
2\. Find a vertex $v_{i}$ that has the largest r-degree, $\forall v_{k}\in
V^{L(v_{i})}\cap v_{k}\neq v_{i},D^{-}_{r}(v_{k})<D^{-}_{r}(v_{i})$, in the
depth level closest to the first level; Find a vertex $v_{j}$ in $P_{v_{i}\to
X}$ that has the largest t-degree, $\forall v_{k}\in V^{L(v_{j})}\cap
v_{k}\neq v_{j},D^{+}_{t}(v_{k})<D^{+}_{t}(v_{j})$, in the depth level closest
to the last level. e.g., in Fig. 5.2 (b), we find that $v_{i}=v_{j}=v_{5}$.
3\. If $Y_{i}=Y$ and $X_{j}=X$, go to step 4. If $Y_{i}\neq Y$ or $X_{j}\neq
X$, then split all the edges and intermediate vertices in $P_{Y_{i}\to
X_{j}}$, i.e. $P_{Y_{i}^{+}\to X_{j}^{-}}$, into a new page from the current
page, go to step 6. e.g., we split Fig. 5.2 (b) into two pages, one of which
is Fig. 5.2 (c), and the edge between $v_{-4}$ and $v_{13}$ is on the other
page. Note that we do not split roots and terminals when splitting pages. All
the roots are still in the same line of the first depth level, and all the
terminals are still in the same line of the last depth level. Different pages
share the same lines of roots and terminals.
4\. If $L(v_{i})=L(v_{j})$ or $(|P_{v_{i}\to v_{j}}|=1)\cap(|p_{v_{i}\to
v_{j}}|=1)$, i.e., $||P_{v_{i}\to v_{j}}||=1$, then separate root-terminal
pairs as follows:
If there are cross-level outgoing edges from root vertices or cross-level
incoming edges to terminal vertices, then, let $E^{\prime}$ be the set of all
outgoing edges that cross most levels from roots, separate $P_{E^{\prime}\to
X^{-}}$ from the current page, or, let $E^{\prime}$ be the set of all incoming
edges that cross most levels to terminals, separate $P_{Y^{+}\to E^{\prime}}$
from the current page. e.g., we separate Fig. 5.1 (c) into Fig. 5.2 (d) and
Fig. 5.2 (e), separate Fig. 5.2 (e) into Fig. 5.2 (g) and Fig. 5.2 (h).
Otherwise, if $L(v_{i})-L(Y)\geq L(X)-L(v_{j})$, select a set of roots
$Y^{\prime}$, separate $P_{Y^{\prime+}\to X^{-}}$; if $L(v_{i})-L(Y)\leq
L(X)-L(v_{j})$, select a set of terminals $X^{\prime}$, separate $P_{Y^{+}\to
X^{\prime-}}$; Go to step 6.
5\. If $L(v_{i})<L(v_{j})$ and $||P_{v_{i}\to v_{j}}||>1$:
split $P_{(V^{L(v_{i})}_{j})^{+}\to(V^{L(v_{j})}_{i})^{-}}$ into a new page
and go to step 6 if corresponding $v_{i}$ and $v_{j}$ can be found in it,
otherwise factorize the vertices and edges in $P_{V^{L(v_{i})}_{j}\to
V^{L(v_{j})}_{i}}$ locally and replace simple chains or simple blocks with
reference edges until $L(v_{i})=L(v_{j})$ or $||P_{v_{i}\to v_{j}}||=1$. e.g.,
we factorize the vertices and edges between $V^{1}$ and $V^{3}$ in Fig. 5.2
(d) and replace simple chains and simple blocks with reference edges, the
result page is Fig. 5.2 (f).
6\. Apply the above process to the separated pages until there is only one
root-terminal pair or no such $v_{i}$ and $v_{j}$ can be found in each page.
Merge the same root-terminal pairs in different pages.

$y_{2}$$y_{1}$$e_{18}$$e_{19}$$e_{3}e_{7}$$e_{4}$$e_{5}$$e_{6}e_{10}$$e_{8}$$e_{9}$$e_{11}$$e_{12}$$e_{15}$$e_{13}$$e_{14}$$e_{16}$$x_{3}$$x_{1}$$x_{2}$$x_{4}$
(a)

Figure 5.3:

$\displaystyle s_{1}=e_{3}e_{7}$ (5.1) $\displaystyle s_{2}=e_{6}e_{10}$ (5.2)
$\displaystyle s_{4}=(e_{8}e_{11}+e_{9}e_{12})$ (5.3) $\displaystyle
s_{5}=e_{18}(s_{1}e_{11}+e_{4}s_{4})=e_{18}(e_{3}e_{7}e_{11}+e_{4}(e_{8}e_{11}+e_{9}e_{12}))$
(5.4) $\displaystyle
s_{6}=e_{19}(s_{2}e_{12}+e_{5}s_{4})=e_{19}(e_{6}e_{10}e_{12}+e_{5}(e_{8}e_{11}+e_{9}e_{12}))$
(5.5) $\displaystyle\frac{\partial v_{-2}}{\partial
v_{12}}=e_{18}(s_{1}+e_{4}e_{8})e_{15}=e_{18}(e_{3}e_{7}+e_{4}e_{8})e_{15}$
(5.6) $\displaystyle\frac{\partial v_{-2}}{\partial
v_{13}}=e_{18}e_{4}e_{9}e_{16}$ (5.7) $\displaystyle\frac{\partial
v_{-2}}{\partial
v_{10}}=s_{5}e_{13}=e_{18}(e_{3}e_{7}e_{11}+e_{4}(e_{8}e_{11}+e_{9}e_{12}))e_{13}$
(5.8) $\displaystyle\frac{\partial v_{-2}}{\partial
v_{11}}=s_{5}e_{14}=e_{18}(e_{3}e_{7}e_{11}+e_{4}(e_{8}e_{11}+e_{9}e_{12}))e_{14}$
(5.9) $\displaystyle\frac{\partial v_{-3}}{\partial
v_{13}}=e_{19}(e_{5}e_{9}+s_{2})e_{16}=e_{19}(e_{5}e_{9}+e_{6}e_{10})e_{16}$
(5.10) $\displaystyle\frac{\partial v_{-3}}{\partial
v_{12}}=e_{19}e_{5}e_{8}e_{15}$ (5.11) $\displaystyle\frac{\partial
v_{-3}}{\partial
v_{10}}=s_{6}e_{13}=e_{19}(e_{6}e_{10}e_{12}+e_{5}(e_{8}e_{11}+e_{9}e_{12}))e_{13}$
(5.12) $\displaystyle\frac{\partial v_{-3}}{\partial
v_{11}}=s_{6}e_{14}=e_{19}(e_{6}e_{10}e_{12}+e_{5}(e_{8}e_{11}+e_{9}e_{12}))e_{14}$
(5.13)

We notice that every edge between two intermediate vertices in line-graph is a
multiplication relation, however in algebraic expressions, there are two types
of multiplication relation: direct and indirect. e.g., in
$e_{18}(e_{3}e_{7}+e_{4}e_{8})e_{15}$, there is a direct multiplication
relation between $e_{4}$ and $e_{8}$, whereas in
$e_{4}(e_{8}e_{11}+e_{9}e_{12})$, the multiplication relation between $e_{4}$
and $e_{8}$ is indirect, there is a parenthesis between $e_{4}$ and $e_{8}$.

Assume we have found the optimal calculation order of a differentiation graph
$G$, which is represented by a set of algebraic expressions connected by
reference variables. In its corresponding line-graph $\tilde{G}$, there may be
different types of multiplication relations in different root-terminal pairs
for the same edge, elimination of which may break parentheses in the optimal
algebraic expressions of some root-terminal pairs, i.e. break the optimal
calculation order. e.g., Fig. 5.3 is the line-graph of Fig. 5.2 (e), we assume
Eq. 5.1 \- Eq. 5.13 is an optimal calculation order. If we eliminate edge
$\langle e_{18},e_{4}\rangle$ directly from Fig. 5.3 for Eq. 5.7, it will
break the calculation order of Eq. 5.6, Eq. 5.8 and Eq. 5.9.

We can fix it by explicitly splitting edges with conflicting multiplication
relations, separating the direct multiplication relation from the indirect,
and only eliminating those edges that represent direct multiplication
relations. However, this method not only copies a lot of vertices and edges,
but also requires more decision-making about how to split and which ones to
eliminate. Furthermore, the splitting of an edge sometimes depends on the
splitting of another adjacent edge, e.g., in Fig. 5.3, the splitting of
$\langle e_{18},e_{4}\rangle$ depends on the splitting of $\langle
e_{4},e_{9}\rangle$.

Another solution is to search for a face elimination sequence without explicit
splitting. Assume we have already known a set of optimal algebraic
expressions, we can eliminate edges in line-graph in the same order as the
calculation order of the corresponding set of optimal algebraic expressions,
avoiding breaking parentheses. Unlike parentheses elimination in an algebraic
expression, the face elimination of a sub-expression block in line-graph may
not only depend on the sub-expression blocks nested in it but also the sub-
expression blocks outside it, because one edge that denotes direct
multiplication relation in a sub-expression block of an expression may denote
indirect multiplication relation in a sub-expression block of another
expression. e.g., the face elimination of $(e_{3}e_{7}+e_{4}e_{8})$ in Eq. 5.6
depends on the face elimination of $e_{8}e_{11}$ in Eq. 5.4. Therefore when
eliminating multiplication relations inside sub-expression blocks, we need to
eliminate those direct multiplication relations that have no indirect
multiplication relations in other sub-expression blocks first. e.g.,
elimination of $\langle e_{8},e_{11}\rangle$ and $\langle e_{9},e_{12}\rangle$
in Fig. 5.3 will not break the optimal calculation order in the algebraic
expression set Eq. 5.1 \- Eq. 5.13.

######  Lemma 1.

Assume that $G(V,E)$ is a differentiation graph, $A$ is one of its
corresponding optimal algebraic expression sets, $s_{1}$, $s_{2}$ are edge or
reference edges in $G$ and $s_{1}\succ s_{2}$. If $s_{1}$ and $s_{2}$ have
both direct and indirect multiplication relations in $A$, then there must be
an edge or reference edge $s_{3}$ in the indirect multiplication relation of
$s_{1}$ and $s_{2}$, such that $s_{1}(s_{2}s_{3}+\Delta s)$ or $(\Delta
s+s_{3}s_{1})s_{2}$, where $\Delta s$ is the rest sub-expressions in the block
and $\Delta s\neq 0\cap s_{3}\notin\Delta s$.

###### Proof.

There are 4 possible forms of indirect multiplication relation for $s_{1}$ and
$s_{2}$: $s_{1}(s_{2}+\Delta s)$, $s_{1}(s_{2}s_{3}+\Delta s)$, $(\Delta
s+s_{1})s_{2}$ and $(\Delta s+s_{3}s_{1})s_{2}$. Assume that $a_{1}\in A\ni
a_{2}$, and $\exists s_{1}(s_{2}+\Delta s)\in a_{1}\cap
s_{i}(s_{1}s_{2}+\Delta s_{a})s_{j}\in a_{2}$, $s_{i}$ is the predecessor of
$(s_{1}s_{2}+\Delta s_{a})$, $s_{j}$ is the successor of $(s_{1}s_{2}+\Delta
s_{a})$, $\Delta s_{a}$ is the sibling of $s_{1}s_{2}$, $s_{i}=1$ if it has no
predecessor, $s_{j}=1$ if it has no successor, $\Delta s_{a}=0$ if it has no
sibling. From the sub-expressions $s_{1}(s_{2}+\Delta s)$ we know that $s_{2}$
and $\Delta s$ have the same source vertex and destination vertex, i.e.,
$s_{2}^{-}=\Delta s^{-}\cap s_{2}^{+}=\Delta s^{+}$, therefore there must be a
sibling sub-expression of $s_{i}(s_{1}s_{2}+\Delta s_{a})s_{j}$, such that
$s_{i}(s_{1}\Delta s+\Delta s_{b})s_{j}+s_{i}(s_{1}s_{2}+\Delta s_{a})s_{j}\in
a_{2}$, where $\Delta s_{b}=0$ if $s_{1}\Delta s$ has no sibling. Obviously,
$s_{i}(s_{1}\Delta s+\Delta s_{b})s_{j}+s_{i}(s_{1}s_{2}+\Delta
s_{a})s_{j}=s_{i}(s_{1}(\Delta s+s_{2})+\Delta s_{b})s_{j}$, the number of
calculation can be reduced, which means $a_{2}$ and $A$ are not optimal.
Therefore, $s_{1}(s_{2}+\Delta s)$ is impossible. Similarly, we can prove
$(\Delta s+s_{1})s_{2}$ is also impossible. ∎

Notice that we can omit $\Delta s$ in the indirect multiplication relations
above, simply use $s_{1}|s_{2}s_{3}$ and $s_{3}s_{1}|s_{2}$ to denote
$s_{1}(s_{2}s_{3}+\Delta s)$ and $(\Delta s+s_{3}s_{1})s_{2}$ respectively.

######  Lemma 2.

Assume that $G(V,E)$ is a differentiation graph, $A$ is one of its
corresponding optimal algebraic expression sets, $s_{1}$, $s_{2}$ are edge or
reference edges in $G$ and $s_{1}\succ s_{2}$. If $s_{1}$ and $s_{2}$ have
both direct and indirect multiplication relations in $A$, then in order to
avoid breaking parentheses between $s_{1}$ and $s_{2}$ in $A$, the face
elimination of $\langle s_{1},s_{2}\rangle$ in line-graph depends on the face
eliminations of all $\langle s_{2},s_{i}\rangle$ that have $s_{1}|s_{2}s_{i}$
in $A$.

###### Proof.

For all the edges $\langle s_{2},s_{i}\rangle$ in line-graph that have
$s_{1}|s_{2}s_{i}$ in $A$, the elimination of $\langle s_{2},s_{i}\rangle$
will implicitly split $s_{2}$ into another vertex and create a new edge
connecting $s_{1}$ to it. ∎

Notice that It is possible for direct and indirect multiplication relations to
form circular structure in an algebraic expression set, because there are two
directions in $s_{1}|s_{2}s_{3}$ and $s_{3}s_{1}|s_{2}$. e.g.,
$s_{1}|s_{2}s_{3}$, $s_{2}|s_{3}s_{4}$, $s_{5}s_{3}|s_{4}$,
$s_{6}s_{5}|s_{3}$, $s_{7}s_{6}|s_{5}$, $s_{8}s_{7}|s_{6}$,
$s_{8}|s_{7}s_{1}$, $s_{7}|s_{1}s_{2}$. It seems impossible for us to
eliminate an edge in the circular dependencies without breaking parentheses.

######  Proposition 1.

Given a differentiation graph, face elimination can achieve optimal Jacobian
accumulation that requires minimum number of calculations if there exists at
least one corresponding optimal algebraic expression set that doesn’t contain
circular elimination dependencies.

###### Proof.

Assume that $G(V,E)$ is a differentiation graph, $A$ is one of its
corresponding optimal algebraic expression sets that doesn’t contain circular
elimination dependencies, $s_{1}$, $s_{2}$ are edge or reference edges in $G$
and $s_{1}\succ s_{2}$. If $s_{1}$ and $s_{2}$ have both direct and indirect
multiplication relations in $A$, then for all the edges $\langle
s_{2},s_{i}\rangle$ in line-graph that have $s_{1}|s_{2}s_{i}$ in $A$, if
$\langle s_{2},s_{i}\rangle$ has no indirect multiplication relation in $A$,
we can eliminate it first, if all $\langle s_{2},s_{i}\rangle$ that have
$s_{1}|s_{2}s_{i}$ in $A$ are eliminated, we can safely eliminate the edge
$\langle s_{1},s_{2}\rangle$ in line-graph without worrying about accidentally
breaking parentheses in any $s_{1}|s_{2}s_{i}$. If $\langle
s_{2},s_{i}\rangle$ also has indirect multiplication relations
$s_{2}|s_{i}s_{j}$ in $A$, we can apply this process to $s_{2}s_{i}$ and
$s_{2}|s_{i}s_{j}$ recursively. ∎

We don’t yet know if it is impossible to form circular dependencies in the
optimal algebraic expression sets of a differentiation graph. If all the
optimal algebraic expression sets of a differentiation graph contain circular
dependencies, we may not be able to achieve optimal by performing face
elimination.

## 6\. Conclusion

There is close correspondence between differentiation graph and algebraic
expression, simple differentiation graph and algebraic expression are
interconvertible provided that the multiplication relations in the algebraic
expressions converted from differentiation graphs are noncommutative.
Differentiation graph is more flexible, it can merge the same intermediate
variable or subexpression that cannot be factored out in algebraic expression.
There is no direct representation or corresponding counterpart of complex
block in algebraic expression. We can factorize overly merged complex blocks
or chains, and transform them into simple differentiation graphs only with
simple chains and simple blocks. For the simple blocks and simple chains,
elimination of paths is equivalent to elimination of corresponding edges and
vertices as long as it follows the optimal calculation order. Local Jacobian
multiplication can automatically factorize complex blocks but it is up to us
to find a better accumulation order. The purpose of multiple blocks or chains
being intertwined together is to merge the same common sub-chains or sub-
blocks, if we know the optimal common sub-chain or sub-block combination set,
we can compute them separately. In line-graph there may be different types of
multiplication relations for the same edge, elimination of which may break the
optimal calculation order. Unlike parentheses elimination in an algebraic
expression, the face elimination of a sub-expression block in line-graph may
not only depend on the sub-expression blocks nested in it but also the sub-
expression blocks outside it. It is possible for direct and indirect
multiplication relations to form circular dependencies in an algebraic
expression set. If all the optimal algebraic expression sets of a
differentiation graph contain circular dependencies, we may not be able to
achieve optimal by performing face elimination.

## References

  * [1] Andrea Walther Andreas Griewank.  Evaluating derivatives : principles and techniques of algorithmic differentiation, 2nd edition, 2008.
  * [2] Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind.  Automatic differentiation in machine learning: a survey, 2015.  https://arxiv.org/abs/1502.05767.
  * [3] A Griewank and U Naumann.  Accumulating jacobians by vertex, edge, or face elimination.  Proceedings of the 6th African Conference on Research in Computer Science, INRIA, France, pages 375–383, 2002.
  * [4] Andreas Griewank and Uwe Naumann.  Accumulating jacobians as chained sparse matrix products.  Math. Prog, 3:2003, 2002.
  * [5] Brian Guenter.  The D* symbolic differentiation algorithm, 2007.
  * [6] Paul Wilhelm Matthias Kuhn.  Edge and vertex elimination, 2009.  https://doi.org/10.1007/s10107-003-0456-9.
  * [7] U Naumann.  Optimal accumulation of jacobian matrices by elimination methods on the dual computational graph, 2003.  https://doi.org/10.1007/s10107-003-0456-9.
  * [8] Uwe Naumann and Jean Utke.  On face elimination in computational graphs, 2017.  http://cerfacs.fr/wp-content/uploads/2017/06/7_Naumann_utke.pdf.
  * [9] Terence Parr and Jeremy Howard.  The matrix calculus you need for deep learning, 2018.  https://arxiv.org/abs/1802.01528.