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

E. Varnik

Sujets

• Informatik
• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2011
• Nombre de lectures: 17
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Exploitation of Structural Sparsity in Algorithmic Differentiation
Von der Fakulta¨t Mathematik, Informatik und Naturwissenschaften
der RWTH Aachen University
zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften genehmigte Dissertation
vorgelegt von
Diplom-Informatiker
Ebadollah Varnik
aus Bandar Torkman, Iran
Berichter : Universita¨tsprofessor Dr. Uwe Naumann
Universita¨tsprofessor Dr. Andrea Walther
Tag der mu¨ndlichen Pru¨fung : 09.11.2011
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfu¨gbar.2Contents
1 Foundations 11
1.1 First and Second-Order Derivative Models . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Vertex Elimination on Computational Graphs . . . . . . . . . . . . . . . . . . . . . . . 13
2 Jacobian Accumulation on Extended Jacobians 21
2.1 Motivation and Summary of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Dense Jacobian Accumulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Trading Fill-Out for Fill-In . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Sparse Jacobian Accumulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4.1 Symbolic Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.2 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5 Parallel Jacobian Accumulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.5.1 Atomic Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.5.2 Pyramid Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.5.3 Master-Slave Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.5.4 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.6 Iterative Jacobian Accumulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.6.1 Iterative Approach on Extended Jacobians . . . . . . . . . . . . . . . . . . . . . 76
2.6.2 Iterative Sparsity Exploitation of Extended Jacobians . . . . . . . . . . . . . . . 80
2.6.3 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3 Detection and Exploitation of Sparsity in Derivative Tensors 97
3.1 Motivation and Summary of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.2 Quantitative Dependence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.2.1 Mathematical Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.2.2 Sparsity Pattern Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.2.3 Computation of Constant Partial Derivatives . . . . . . . . . . . . . . . . . . . . 105
3.2.4 Case Study I : Sparse Jacobian Computation . . . . . . . . . . . . . . . . . . . 110
3.2.5 Case Study II : Sparse Hessian Computation . . . . . . . . . . . . . . . . . . . 114
3.2.6 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.3 Conservative Hessian Pattern Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 122
3.3.1 Exact Hessian Pattern Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 122
3.3.2 Exploitation of Partial Separability . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.3.3 Recursive Hessian Pattern Estimation . . . . . . . . . . . . . . . . . . . . . . . 127
3.3.4 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4 Summary and Conclusion 139
34 CONTENTSList of Symbols
AD Algorithmic Differentiation . . . . . . . . . . . . . . . . . . . . . . . 11
F Multivariate Vector Function . . . . . . . . . . . . . . . . . . . . . . 11
n Number of Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
m Number of Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
x Input Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
y Output Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
SAC Single Assignment Code . . . . . . . . . . . . . . . . . . . . . . . . 11
q Number of SAC Variables . . . . . . . . . . . . . . . . . . . . . . . 11
v SAC Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11j
ij Direct Dependence ofv onv . . . . . . . . . . . . . . . . . . . . . 11j i
ϕ Elemental Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 11j
P Number of Arguments ofϕ . . . . . . . . . . . . . . . . . . . . . . 11j j
S Number of Elemental Functions havingv as Argument . . . . . . . . 11j j
TLM Tangent-Linear Model . . . . . . . . . . . . . . . . . . . . . . . . . 12
ADM Adjoint Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
TLVM Tangent-Linear Vector Model . . . . . . . . . . . . . . . . . . . . . . 12
ADVM Adjoint Vector Model . . . . . . . . . . . . . . . . . . . . . . . . . . 12
SOTLM Second-Order Tangent-Linear Model . . . . . . . . . . . . . . . . . . 12
SOADM Second-Order Adjoint Model . . . . . . . . . . . . . . . . . . . . . . 13
DAG Directed Acyclic Graph . . . . . . . . . . . . . . . . . . . . . . . . . 13
G Linearized Computational Graph ofF . . . . . . . . . . . . . . . . . 13
V Index Set denoting Vertices ofG [SAC Variables] . . . . . . . . . . . 13
E Index Pair Set denoting Edges ofG . . . . . . . . . . . . . . . . . . 13
X Index Set of Independent Vertices [SAC Variables] . . . . . . . . . . 14
p Number of Intermediate DAG Vertices [SAC Variables] . . . . . . . . 14
Z Index Set of Intermediate Vertices [SAC Variables] . . . . . . . . . . 14
Y Index Set of Dependent Vertices [SAC Variables] . . . . . . . . . . . 14
c Local Partial Derivative ofv with respect tov . . . . . . . . . . . . 14j,i j i
l-DAG Linearized DAG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
˜G G after Elimination of all intermediate Vertices . . . . . . . . . . . . 14
˜ ˜V Vertices ofG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
˜ ˜E Edges ofG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
G j Elimination of Vertexj fromG . . . . . . . . . . . . . . . . . . . . . 14
G (j,k) Back-Elimination of Edge(j,k) fromG . . . . . . . . . . . . . . . . 14
Mark(j) Markowitz Degree of Vertexj . . . . . . . . . . . . . . . . . . . . . 15
μ Amount of Storage in Bits for an Edge . . . . . . . . . . . . . . . . . 18e
μ Amount of Storage in Bits for a Vertex . . . . . . . . . . . . . . . . . 18v
56 LIST OF SYMBOLS
μ Amount of Storage in Bits for a Floating Point Value . . . . . . . . . 18F
DEJ Dense Extended Jacobian . . . . . . . . . . . . . . . . . . . . . . . . 24
0C Extended Jacobian Matrix . . . . . . . . . . . . . . . . . . . . . . . 25
DJARE Dense Jacobian Accumulation by Row Elimination . . . . . . . . . . 26
0˜C Eliminated Extended Jacobian . . . . . . . . . . . . . . . . . . . . . 26
Nonzero Entry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
+ Absorption of a Nonzero Entry . . . . . . . . . . . . . . . . . . . . . 31
~ Fill-in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Absorption of a Fill-in . . . . . . . . . . . . . . . . . . . . . . . . . 31

Fill-out reused for Fill-in . . . . . . . . . . . . . . . . . . . . . . . . 31
} Fill-out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
SJARE Sparse Jacobian Accumulation by Row Elimination . . . . . . . . . . 35
CRS Compressed Row Storage . . . . . . . . . . . . . . . . . . . . . . . . 35
nz Number of Nonzeros . . . . . . . . . . . . . . . . . . . . . . . . . . 35
0(α,κ,ρ) CRS Representation ofC . . . . . . . . . . . . . . . . . . . . . . . 36
(α˜,κ˜,ρ˜) (α,κ,ρ) after Elimination of all intermediate Rows . . . . . . . . . . 36
μ Amount of Storage in Bits for an Interger Value . . . . . . . . . . . . 40I
BP Bit Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
GFM Global (Non-Iterative) Forward Mode . . . . . . . . . . . . . . . . . 47
GRM Global (Non-Iterative) Reverse Mode . . . . . . . . . . . . . . . . . 47
PJA Parallel Jacobian Accumulation . . . . . . . . . . . . . . . . . . . . . 53
G(S) Composition DAG ofjSj Atomic Subgraphs . . . . . . . . . . . . . . 56
LFM Local Forward Mode . . . . . . . . . . . . . . . . . . . . . . . . . . 62
LRM Local Reverse Mode . . . . . . . . . . . . . . . . . . . . . . . . . . 62
DP Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . 62
IRM Iterative Reverse Mode . . . . . . . . . . . . . . . . . . . . . . . . . 90
IFM Iterative Forward Mode . . . . . . . . . . . . . . . . . . . . . . . . . 90
ALE Assignment Level Elimination . . . . . . . . . . . . . . . . . . . . . 90
EHP Exact Hessian Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . 98
QDA Quantitative Dependence Analysis . . . . . . . . . . . . . . . . . . . 99
TSP Tensor Sparsity Pattern . . . . . . . . . . . . . . . . . . . . . . . . . 102
OPS(F) Number of Performed Floating Point Operations inF. . . . . . . . . . 105
TCE Tensor Constant Estimation . . . . . . . . . . . . . . . . . . . . . . . 108
SJC Sparse Jacobian Computation . . . . . . . . . . . . . . . . . . . . . . 110
SHC Sparse Hessian Computation . . . . . . . . . . . . . . . . . . . . . . 116
SMB Simulated Moving Bed . . . . . . . . . . . . . . . . . . . . . . . . . 121
CHP