Publication: Capitalizing on live variables: new algorithms for efficient Hessian computation via automatic differentiation
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Capitalizing on live variables: new algorithms for efficient Hessian computation via automatic differentiation

- Article in a journal -
 

Author(s)
Mu Wang , Assefaw Gebremedhin , Alex Pothen

Published in
Mathematical Programming Computation

Year
2016

Abstract
We revisit an algorithm [called Edge Pushing (EP)] for computing Hessians using Automatic Differentiation (ad) recently proposed by Gower and Mello (Optim Methods Softw 27(2): 233--249, 2012). Here we give a new, simpler derivation for the EP algorithm based on the notion of live variables from data-flow analysis in compiler theory and redesign the algorithm with close attention to general applicability and performance. We call this algorithm Livarh and develop an extension of Livarh that incorporates preaccumulation to further reduce execution time---the resulting algorithm is called Livarhacc. We engineer robust implementations for both algorithms Livarh and Livarhacc within ADOL-C, a widely-used operator overloading based ad software tool. Rigorous complexity analyses for the algorithms are provided, and the performance of the algorithms is evaluated using a mesh optimization application and several kinds of synthetic functions as testbeds. The results show that the new algorithms outperform state-of-the-art sparse methods (based on sparsity pattern detection, coloring, compressed matrix evaluation, and recovery) in some cases by orders of magnitude. We have made our implementation available online as open-source software and it will be included in a future release of ADOL-C.

AD Theory and Techniques
Hessian

BibTeX
@ARTICLE{
         Wang2016Col,
       author = "Wang, Mu and Gebremedhin, Assefaw and Pothen, Alex",
       title = "Capitalizing on live variables: new algorithms for efficient {H}essian computation via
         automatic differentiation",
       journal = "Mathematical Programming Computation",
       volume = "8",
       number = "4",
       pages = "393--433",
       abstract = "We revisit an algorithm [called Edge Pushing (EP)] for computing Hessians using
         Automatic Differentiation (AD) recently proposed by Gower and Mello (Optim Methods Softw 27(2):
         233--249, 2012). Here we give a new, simpler derivation for the EP algorithm based on the notion of
         live variables from data-flow analysis in compiler theory and redesign the algorithm with close
         attention to general applicability and performance. We call this algorithm Livarh and develop an
         extension of Livarh that incorporates preaccumulation to further reduce execution time---the
         resulting algorithm is called Livarhacc. We engineer robust implementations for both algorithms
         Livarh and Livarhacc within ADOL-C, a widely-used operator overloading based AD software tool.
         Rigorous complexity analyses for the algorithms are provided, and the performance of the algorithms
         is evaluated using a mesh optimization application and several kinds of synthetic functions as
         testbeds. The results show that the new algorithms outperform state-of-the-art sparse methods (based
         on sparsity pattern detection, coloring, compressed matrix evaluation, and recovery) in some cases
         by orders of magnitude. We have made our implementation available online as open-source software and
         it will be included in a future release of ADOL-C.",
       issn = "1867-2957",
       doi = "10.1007/s12532-016-0100-3",
       url = "https://doi.org/10.1007/s12532-016-0100-3",
       year = "2016",
       ad_theotech = "Hessian"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)