Livarh swMATH ID: 31778 Software Authors: Wang, Mu; Gebremedhin, Assefaw; Pothen, Alex Description: Capitalizing on live variables: new algorithms for efficient Hessian computation via automatic differentiation. 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. .. 5.2 Implementing Livarh Homepage: http://mpc.zib.de/archive/2016/4/Wang2016_Article_CapitalizingOnLiveVariablesNew.pdf Source Code: https://github.com/CSCsw/LivarH Keywords: algorithmic differentiation; Hessian computation; reverse mode AD; edge pushing; ADOL-C; data-flow analysis Related Software: Livarhacc; edge_push_sp; ColPack; MatrixCalculus; L-BFGS; TADIFF; FADBAD++; NUTS; torchdiffeq; JuMP; Julia; ve08; LIBSVM; AMPL; hess_pat; dcc; Valgrind; ADOL-C Cited in: 3 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Capitalizing on live variables: new algorithms for efficient Hessian computation via automatic differentiation. Zbl 1391.90582Wang, Mu; Gebremedhin, Assefaw; Pothen, Alex 2016 all top 5 Cited by 10 Authors 1 Gebremedhin, Assefaw Hadish 1 Huchette, Joey 1 Huot, Mathieu 1 Lubin, Miles 1 Petra, Cosmin G. 1 Pothen, Alex 1 Qiang, Fangwei 1 Staton, Sam 1 Vákár, Matthijs 1 Wang, Mu Cited in 3 Serials 1 Optimization Methods & Software 1 Logical Methods in Computer Science 1 Mathematical Programming Computation Cited in 5 Fields 2 Numerical analysis (65-XX) 2 Operations research, mathematical programming (90-XX) 1 Mathematical logic and foundations (03-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Computer science (68-XX) Citations by Year