Publications

U. Naumann and J. Utke, "Reduction of Edge Labeled DAGs through Constant Folding," Preprint ANL/MCS-P1073-0803, September 2003. [pdf]

We present intermediate results for a discrete problem arising in the automatic generation of derivative code. Consider a directed acyclic graph (dag) G = (V,E) with vertex set V = X u Z u Y, where X is the set of minimal vertices, Z is the set of intermediate vertices, Y is the set of maximal vertices, and E is the set of edges (i,j) with i,j in V. X, Y, and Z are pairwise disjoint. The vertices are numbered such that they induce a dependency order, (i,j) in E => i < j. Each edge (i,j) is annotated with a label c[sub ji] in R. The c[sub ji] can be categorized as either variable or constant. G is transformed into a bipartite graph by using a sequence \sigma of edge (front and back) and vertex eliminations.