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

Sanjukta Bhowmick; Paul D. Hovland

doi:10.1007/978-3-540-68942-3_9

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 proceeding › Conference contribution

4 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 language	English (US)
Title of host publication	Advances in Automatic Differentiation
Pages	91-102
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-540-68942-3_9
State	Published - 2008
Externally published	Yes
Event	5th International Conference on Automatic Differentiation - Bonn, Germany Duration: Aug 11 2008 → Aug 15 2008

Publication series

Name	Lecture Notes in Computational Science and Engineering
Volume	64 LNCSE
ISSN (Print)	1439-7358

Conference

Conference	5th International Conference on Automatic Differentiation
Country/Territory	Germany
City	Bonn
Period	8/11/08 → 8/15/08

Keywords

Directed acyclic graph
Hessian computational graphs
Symmetry

ASJC Scopus subject areas

Modeling and Simulation
General Engineering
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Mathematics

Access to Document

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

Cite this

Bhowmick, S & Hovland, PD 2008, A polynomial-time algorithm for detecting directed axial symmetry in Hessian computational graphs. in Advances in Automatic Differentiation. Lecture Notes in Computational Science and Engineering, vol. 64 LNCSE, pp. 91-102, 5th International Conference on Automatic Differentiation, Bonn, Germany, 8/11/08. https://doi.org/10.1007/978-3-540-68942-3_9

@inproceedings{03bb0d4c93fd4e24b08c97a8c2287fa3,

title = "A polynomial-time algorithm for detecting directed axial symmetry in Hessian computational graphs",

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.",

keywords = "Directed acyclic graph, Hessian computational graphs, Symmetry",

author = "Sanjukta Bhowmick and Hovland, {Paul D.}",

year = "2008",

doi = "10.1007/978-3-540-68942-3_9",

language = "English (US)",

isbn = "9783540689355",

series = "Lecture Notes in Computational Science and Engineering",

pages = "91--102",

booktitle = "Advances in Automatic Differentiation",

note = "5th International Conference on Automatic Differentiation ; Conference date: 11-08-2008 Through 15-08-2008",

}

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 -

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this