LANS Publications

"A Polynomial Time Algorithm for the Detection of Axial Symmetry in Directed Acyclic Graphs"

S. Bhowmick and P. Hovland

. Also Preprint ANL/MCS-P1314-0106

Preprint Version: [pdf]

Computation of Hessians in automatic differentiation can be done by applying elimination techniques on a symmetric computational graph. Detection of symmetry in the graph, i.e. matching the vertices and edges with their corresponding pairs can enable us to identify duplicate mirror operations. We can exploit symmetry by performing only one of each of these duplicate operations and thus greatly reduce the computation costs, by almost halving the number of operations. In this paper we present a polynomial time algorithm that can detect symmetry in directed acyclic graphs. We prove the correctness of the algorithm and demonstrate with an example how detection of symmetry lowers the cost of computing Hessians.