Exploitation of structural sparsity in algorithmic differentiation [Elektronische Ressource] / Ebadollah Varnik

Exploitation of Structural Sparsity in Algorithmic DifferentiationVon der Fakulta¨t Mathematik, Informatik und Naturwissenschaftender RWTH Aachen Universityzur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-InformatikerEbadollah Varnikaus Bandar Torkman, IranBerichter : Universita¨tsprofessor Dr. Uwe NaumannUniversita¨tsprofessor Dr. Andrea WaltherTag der mu¨ndlichen Pru¨fung : 09.11.2011Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfu¨gbar.2Contents1 Foundations 111.1 First and Second-Order Derivative Models . . . . . . . . . . . . . . . . . . . . . . . . . 111.2 Vertex Elimination on Computational Graphs . . . . . . . . . . . . . . . . . . . . . . . 132 Jacobian Accumulation on Extended Jacobians 212.1 Motivation and Summary of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.2 Dense Jacobian Accumulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3 Trading Fill-Out for Fill-In . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.4 Sparse Jacobian Accumulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.4.1 Symbolic Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402.4.2 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.5 Parallel Jacobian Accumulation . . . . . . . . . . . . . . . . . . . . . . . . . . . .