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"
}