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

Sanjukta Bhowmick, Paul D. Hovland

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAdvances in Automatic Differentiation
Pages91-102
Number of pages12
DOIs
StatePublished - 2008
Event5th International Conference on Automatic Differentiation - Bonn, Germany
Duration: Aug 11 2008Aug 15 2008

Publication series

NameLecture Notes in Computational Science and Engineering
Volume64 LNCSE
ISSN (Print)1439-7358

Conference

Conference5th International Conference on Automatic Differentiation
CountryGermany
CityBonn
Period8/11/088/15/08

Keywords

  • Directed acyclic graph
  • Hessian computational graphs
  • Symmetry

ASJC Scopus subject areas

  • Modeling and Simulation
  • Engineering(all)
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Mathematics

Fingerprint Dive into the research topics of 'A polynomial-time algorithm for detecting directed axial symmetry in Hessian computational graphs'. Together they form a unique fingerprint.

  • Cite this

    Bhowmick, S., & Hovland, P. D. (2008). A polynomial-time algorithm for detecting directed axial symmetry in Hessian computational graphs. In Advances in Automatic Differentiation (pp. 91-102). (Lecture Notes in Computational Science and Engineering; Vol. 64 LNCSE). https://doi.org/10.1007/978-3-540-68942-3_9