TY - GEN

T1 - A polynomial-time algorithm for detecting directed axial symmetry in Hessian computational graphs

AU - Bhowmick, Sanjukta

AU - Hovland, Paul D.

PY - 2008

Y1 - 2008

N2 - We present a polynomial-time algorithm to improve the performance of computing the Hessian of a vector-valued function. The values of the Hessian derivatives are calculated by applying face, edge, or vertex elimination operations on a symmetric computational graph. Our algorithm detects symmetry in the graph by matching the vertices and edges with their corresponding pairs; thereby enabling us to identify duplicate operations. Through the detection of symmetry, the computation costs can potentially be halved by performing only one of each of these operations.

AB - We present a polynomial-time algorithm to improve the performance of computing the Hessian of a vector-valued function. The values of the Hessian derivatives are calculated by applying face, edge, or vertex elimination operations on a symmetric computational graph. Our algorithm detects symmetry in the graph by matching the vertices and edges with their corresponding pairs; thereby enabling us to identify duplicate operations. Through the detection of symmetry, the computation costs can potentially be halved by performing only one of each of these operations.

KW - Directed acyclic graph

KW - Hessian computational graphs

KW - Symmetry

UR - http://www.scopus.com/inward/record.url?scp=78651544997&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78651544997&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-68942-3_9

DO - 10.1007/978-3-540-68942-3_9

M3 - Conference contribution

AN - SCOPUS:78651544997

SN - 9783540689355

T3 - Lecture Notes in Computational Science and Engineering

SP - 91

EP - 102

BT - Advances in Automatic Differentiation

T2 - 5th International Conference on Automatic Differentiation

Y2 - 11 August 2008 through 15 August 2008

ER -