Parallel Algorithms in Computational Science and Engineering

Preface......Page 6
Part 1: High-Performance Algorithms......Page 8
Part 2: High-Performance Computational Science and Engineering Applications......Page 9
Contents......Page 12
Part I High Performance Algorithms......Page 14
1 Introduction......Page 15
2 Maximum Weight Matching......Page 16
3 Symbolic Symmetric Reordering Techniques......Page 21
3.1 Multilevel Nested Dissection......Page 22
3.1.1 Coarsening Phase......Page 23
3.1.3 Uncoarsening Phase......Page 24
3.2 Other Reordering Methods......Page 25
4 Sparse LU Decomposition......Page 26
4.1 The Elimination Tree......Page 27
4.2 The Supernodal Approach......Page 32
5 Sparse Direct Solvers—Supernodal Data Structures......Page 35
6 Application—Circuit Simulation......Page 37
References......Page 43
1 Introduction......Page 46
2.1 Graph Partitioning by Vertex Separator (GPVS)......Page 48
2.2 Hypergraph Partitioning (HP)......Page 49
3 Singly-Bordered Block-Diagonal Form......Page 50
4 Doubly-Bordered Block-Diagonal Form......Page 55
5 Nonempty Off-Diagonal Block Minimization......Page 59
6 Block-Diagonal Form with Overlap......Page 62
6.1 BDO Form......Page 63
6.2 BDCO Form......Page 67
7 Conclusions......Page 70
References......Page 71
1 Introduction......Page 74
2 IP Algorithm......Page 75
2.1 Search Direction Computation......Page 80
2.2 Backtracking Line-Search Filter Method......Page 82
2.3 Inertia Correction and Curvature Detection......Page 84
2.4.1 Monotone and Adaptive Strategies......Page 85
2.4.3 Quality Function......Page 86
2.5 Problem Scaling and Convergence Criteria......Page 87
3 IP Methods for OPF Problems......Page 88
3.1 Optimal Power Flow......Page 89
3.2 Structure-Exploiting IP Methods—Security Constrained and Multiperiod OPF......Page 90
3.3 Impact of Slack Variables Elimination......Page 92
4.1 Revealing the Structure of SCOPF and MPOPF Problems......Page 93
4.2 Schur Complement Decomposition......Page 97
4.3 Structure-Exploiting Algorithms for MPOPF......Page 100
5 Results and Discussion......Page 102
References......Page 103
1 Introduction......Page 105
2 The SPIKE for Banded Linear Systems (Dense Within the Band)......Page 106
2.1 Multithreaded SPIKE......Page 112
3.1 Weighted Nonsymmetric and Symmetric Reorderings for Sparse Matrices......Page 114
3.2 PSPIKE_NBP......Page 118
3.3 SPIKE_MBP......Page 122
3.4 SPIKE_WBP......Page 123
3.5 The General SPIKE......Page 124
4 Conclusions......Page 128
References......Page 129
Part II High Performance Computational Science and Engineering Applications......Page 131
1 Introduction......Page 132
2 Quantum Descriptions of Matter......Page 133
3.1 The Kohn–Sham Equation......Page 136
3.3.1 Plane waves......Page 138
3.3.3 Real-Space Methods......Page 139
3.4 Comparison of Discretization Approaches......Page 142
3.5 Computing the Electron Density......Page 143
4.1 Traditional Methods: Subspace Iteration, Lanczos, and Davidson......Page 144
4.2 Nonlinear Chebyshev Filtered Subspace Iteration......Page 146
4.3 EVSL: Filtering and Spectrum Slicing......Page 148
4.4 FEAST: Rational Filtering and Spectrum Slicing......Page 151
5 Conclusion......Page 154
References......Page 155
1 Introduction......Page 160
1.1 Space–Time Stabilized and VMS Methods......Page 162
1.2 ALE Stabilized and VMS Methods......Page 163
1.3 Slip Interface Space–Time Method......Page 164
1.4 Immersogeometric VMS Analysis......Page 165
1.7 Topology Change Slip Interface Space–Time Method......Page 166
1.8 Space–Time IGA......Page 167
1.9 Space–Time IGA with Slip Interface and Topology Change......Page 168
1.10 General-Purpose NURBS Mesh Generation Method......Page 169
2.1 Incompressible Flow......Page 170
2.3 Fluid–Structure Interface......Page 171
3 ST-VMS and ST-SI......Page 172
4 ALE-VMS and ALE-IMGA-VMS......Page 174
6.2 Mesh, Flow Conditions and Computational Conditions......Page 176
7.1 Conditions......Page 179
7.2 Mesh......Page 182
7.3 Mesh Refinement Study......Page 184
8 IMGA Computation: Patient-Specific Heart Valve Design and Analysis......Page 188
8.1 Trivariate NURBS Parameterization of the Ascending Aorta......Page 189
8.2 Parametric BHV Design......Page 191
8.3 Application to BHV Design......Page 192
9 Concluding Remarks......Page 194
References......Page 196
1 Introduction......Page 203
1.1 ST-VMS and ST-SUPS......Page 204
1.3 ALE-SI and ST-SI......Page 205
1.5 ST-IGA......Page 206
1.6 ST-SI-IGA......Page 207
1.7 General-Purpose NURBS Mesh Generation Method......Page 208
2.1 Incompressible Flow......Page 209
2.2 Structural Mechanics......Page 210
3 ST-VMS and ST-SI......Page 211
4 ALE-VMS......Page 213
5.1 String Dynamics......Page 214
5.2 Particle Residence Time......Page 215
5.3 Rotation Representation with Constant Angular Velocity......Page 216
7.1 Flow Analysis of the Pump......Page 217
7.2 String Dynamics in the Pump......Page 218
7.4 Discussion......Page 219
8 ST Computation: Aerodynamics of a VAWT......Page 220
8.1 2D Computations......Page 225
8.2 3D Computation......Page 226
9 ALE Computation: HAWT FSI with Rotor–Tower Coupling......Page 227
9.1 Formulation of the Rotor–Tower Penalty Coupling......Page 231
9.2 Rotor and Tower Models and Meshes......Page 233
9.3 Results......Page 235
10 Concluding Remarks......Page 236
References......Page 237
1 Introduction......Page 242
1.1 ST-VMS and ST-SUPS......Page 243
1.3 ALE-SI and ST-SI......Page 244
1.4 Stabilization Parameters......Page 245
1.6 ST-IGA......Page 246
1.7 ST-SI-IGA......Page 247
1.8 MDM......Page 248
1.9 ST-C......Page 249
1.10.2 Thermo-Fluid Analysis of a Freight Truck and Its Rear Set of Tires......Page 250
1.11 Outline of the Remaining Sections......Page 251
2 Governing Equations......Page 252
2.1 Structural Mechanics......Page 253
3 Thermo-Fluid ST-VMS......Page 254
4 ALE-VMS......Page 256
5.1 YZβ DC......Page 259
5.3 Spatially Multiscale MDM......Page 260
7 ST Computation: Aerodynamic Analysis of a Ram-Air Parachute......Page 261
7.1 Structural Mechanics Computation......Page 262
7.2 Fluid Mechanics Computations......Page 264
8 ST Computation: Thermo-Fluid Analysis of a Freight Truck and Its Rear Set of Tires......Page 267
8.1 Problem Setup......Page 268
8.2 Computations and Results......Page 271
9.1 Computational Setup and Boundary Conditions......Page 274
9.2 Aerodynamics Simulation......Page 276
9.3 FSI Simulation......Page 280
10 Concluding Remarks......Page 281
References......Page 282
1 Plan of the Chapter......Page 288
2 On a Multiscale Vision of Crowd Dynamics (Key Problem 1)......Page 290
3 On a Systems Approach to Crowds Modeling (Key Problem 2)......Page 296
4 Parallel Computing and Artificial Intelligence (Key Problem 3)......Page 297
5 Closure......Page 299
References......Page 300
1 Introduction: Weather and HPC......Page 303
2 History......Page 306
3 Models, Grids, and Parallelization......Page 309
3.1 Spectral Dynamics......Page 310
3.2 Grid-Point Dynamics......Page 313
3.2.1 Domain Decomposition......Page 315
3.2.2 Load Imbalance......Page 316
3.3 Element-Based Dynamics......Page 318
3.4 Physics......Page 319
4 Challenges for Next-Generation HPC......Page 321
4.1 Next Generation HPC and the Programming Challenge......Page 323
5 Summary......Page 326
References......Page 327
1 Introduction......Page 330
2 The PageRank and AllPageRank Problem......Page 332
3 PageRank Algorithms......Page 333
3.2 Gauss–Seidel......Page 334
3.3 The Cyclic Push Method......Page 338
3.5 Related Algorithmic Advances......Page 340
4 Results......Page 342
4.2 Performance on a 64-Core System......Page 343
4.4 Performance on a 192-Core System......Page 345
4.5 Performance Scaling......Page 346
5 Related Problems......Page 347
6 Conclusion......Page 348
References......Page 349
1 Introduction......Page 352
2.1 PEC Scatterers......Page 354
2.4 Inhomogeneous Dielectrics......Page 357
3.1 Accurate Space-Time Discretization......Page 358
3.2 Stabilized TDIE Solvers......Page 359
3.3 Well-Conditioned TDIE Solvers......Page 360
4 Fast TDIE Solvers......Page 361
4.2 NGTD......Page 362
4.3 PWTD......Page 363
5.1 Overview of Parallel PWTD......Page 367
5.2 Parallelization of PWTD Stages......Page 368
5.3 Asynchronous Task Queue-Based Communication Scheme......Page 371
6 Applications......Page 372
7 Conclusion......Page 377
References......Page 378
Parallel Optimization Techniques for Machine Learning......Page 385
1 Introduction and Motivation......Page 386
2 Related Research......Page 388
3 Notation and Assumptions......Page 391
4 Convex Optimization Problems......Page 392
4.1 Experimental Results......Page 396
4.1.3 Newsgroups20 Dataset......Page 397
4.2 Sensitivity to Hyper-Parameter Tuning......Page 400
5 Non-convex Optimization......Page 401
5.1 Natural Gradient Computation......Page 402
5.2 Natural Gradient Using Kronecker Factored Approximate Curvature Matrix:......Page 403
5.4 Experimental Results......Page 405
6 Distributed Higher-Order Methods......Page 411
6.1 ADMM Residuals and Stopping Criteria:......Page 413
6.3 Comparison with Distributed First-Order Methods......Page 414
6.4 Comparison with Distributed Second-Order Methods......Page 415
7 Concluding Remarks......Page 417
References......Page 418