Combinatorial Scientific Computing

Cover

Combinatorial Scientific Computing

ISBN 9781439827352

Contents

Foreword

Editors

Contributors

Chapter 1 Combinatorial Scientific Computing: Past Successes, Current Opportunities, Future Challenges

1.1 Introduction
1.2 The CSC Community
1.2.1 The Roots of the CSC Community
1.2.2 Organization of the CSC Community
1.3 Current Opportunities
1.4 Future Challenges
1.4.1 Trends in High Performance Architectures
1.4.2 Trends in Traditional Applications
1.4.3 Emerging Applications
o 1.4.3.1 Data-Centric Scientific Computing
o 1.4.3.2 Computing in the Social Sciences
1.4.4 Biological Applications
o 1.4.4.1 Population Genomics
o 1.4.4.2 Computational Systems Biology
o 1.4.4.3 Next Generation Sequencing
1.5 Conclusions
Acknowledgments
Bibliography

Chapter 2 Combinatorial Problems in Solving Linear Systems

2.1 Introduction
2.2 Basics
2.3 Direct Methods
2.3.1 Labelling or Ordering
2.3.2 Matching and Scaling
2.3.3 Elimination Tree and the Multifrontal Method
o 2.3.3.1 Elimination Tree
o 2.3.3.2 Multifrontal Method
2.3.4 Block Triangular Form
2.4 Iterative Methods
2.4.1 Preconditioners Based on Incomplete Factorization
o 2.4.1.1 Orderings and Their E ects
o 2.4.1.2 Parallelization
2.4.2 Support Graph Preconditioners
2.4.3 Algebraic Multigrid Preconditioning
2.5 Conclusions
Acknowledgments
Bibliography

Chapter 3 Combinatorial Preconditioners

3.1 Introduction
3.2 Symmetric Diagonally-Dominant Matrices and Graphs
3.2.1 Incidence Factorizations of Diagonally-Dominantt Matrices
3.2.2 Graphs and Their Laplacian Matrices
3.3 Support Theory
3.3.1 From Generalized Eigenvalues to Singular Values
3.3.2 The Symmetric Support Lemma
3.3.3 Norm Bounds
3.3.4 Support Numbers
3.3.5 Splitting
3.4 Embeddings and Combinatorial Support Bounds
3.4.1 Defining W Using Path Embeddings
3.4.2 Combinatorial Support Bounds
3.4.3 Subset Preconditioners
3.4.4 Combinatorial Trace Bounds
3.5 Combinatorial Preconditioners
Bibliography

Chapter 4 A Scalable Hybrid Linear Solver Based on Combinatorial Algorithms

4.1 Introduction
4.2 PSPIKE--A Scalable Hybrid Linear Solver
4.2.1 The PSPIKE Algorithm
4.2.2 Preconditioning
4.3 Combinatorics in the Hybrid Solver PSPIKE
4.3.1 Graph Partitioning
o 4.3.1.1 Partitioning and Ordering
o 4.3.1.2 Ordering and Partitioning
4.3.2 Graph Matching
o 4.3.2.1 Parallel Approximation Algorithms
o 4.3.2.2 Simplex-Based Algorithms
o 4.3.2.3 Parallel Primal-Dual Methods
4.3.3 Quadratic Knapsack Problem
o 4.3.3.1 Heuristics
o 4.3.3.2 An Upper Bound and Evaluation of the Heuristics
4.4 Computational Results in PDE-Constrained Optimization
4.5 Conclusions
Bibliography

Chapter 5 Combinatorial Problems in Algorithmic Differentiation

5.1 Introduction
5.2 Compression Techniques
5.2.1 Computation of Sparse Jacobians
5.2.2 Computation of Sparse Hessians
5.2.3 Open Problems
5.3 Data Flow Reversal
5.3.1 Call Tree Reversals
5.3.2 Reversals of (Pseudo-) Timestepping Procedures
5.4 Elimination Techniques
5.4.1 Vertex Elimination
5.4.2 Edge Elimination
5.4.3 Face Elimination
5.4.4 Computational Complexity
5.4.5 Open Problems
5.5 Summary and Conclusion
Bibliography

Chapter 6 Combinatorial Problems in OpenAD

6.1 Introduction
6.2 Computational Graphs
6.2.1 Problem Representation
6.2.2 Elimination Heuristics
6.2.3 Scarcity-Preserving Heuristics
6.3 Reversal Schemes
6.3.1 Simple Split and Joint Modes
6.3.2 Template Mechanism
6.3.3 Reversal Scheme Using Revolve
Acknowledgments
Bibliography

Chapter 7 Getting Started with ADOL-C

7.1 Introduction
7.2 Preparing a Code Segment for Differentiation
7.3 Easy-to-Use Drivers
7.4 Reusing the Pre-Value Tape for Arbitrary Input Values
7.5 Suggestions for Improved Eciency
7.6 Advance Algorithmic Differentiation in ADOL-C
7.7 Tapeless Forward Differentiation
7.8 Conclusions and Further Developments
Bibliography

Chapter 8 Algorithmic Differentiation and Nonlinear Optimization for an Inverse Medium Problem

8.1 Introduction
8.2 The Inverse Medium Problem
8.2.1 Computational Wave Propagation
8.2.2 Inverse Medium Problem Formulation
8.3 Large-Scale Nonlinear Optimization and IPOPT
8.4 Closed Form of Derivatives
8.5 Algorithmic Differentiation
8.5.1 Derivative Codes by dcc
8.5.2 Detection and Exploitation of Sparsity
8.6 Sparse Linear Algebra and PARDISO
8.6.1 Graph-Based Pivoting Methods
8.7 Numerical Experiments
Bibliography

Chapter 9 Combinatorial Aspects/Algorithms in Computational Fluid Dynamics

9.1 System of Conservation Laws
9.2 Grid Size Estimates
9.3 Work Estimates for Different Shape-Functions
9.3.1 Work Estimates for Linear Problems
9.3.2 Work Estimates for Nonlinear Problems
9.3.3 Possible Objections
9.4 Basic Data Structures and Loops
9.4.1 Basic Loop
9.4.2 Vector Machines
9.4.3 Shared Memory Multicore Machines
9.4.4 Distributed Memory Machines
9.5 Example: Blast in Room
9.6 Conclusions and Outlook
Bibliography

Chapter 10 Unstructured Mesh Generation

10.1 Introduction
10.2 Meshes
10.2.1 Domain Conformity
10.2.2 What Is a Good Element?
10.3 Methods of Mesh Generation
10.3.1 Advancing Front Mesh Generation
o 10.3.1.1 A Generic Advancing Front Method
o 10.3.1.2 Some Speci c Algorithms
10.3.2 Delaunay Mesh Generation
o 10.3.2.1 Delaunay and Constrained Delaunay Triangulations
o 10.3.2.2 Algorithms for Constructing Delaunay Triangulations
o 10.3.2.3 A Generic Delaunay Re nement Algorithm
o 10.3.2.4 Some Speci c Algorithms
10.3.3 Grid, Quadtree, and Octree Mesh Generation
o 10.3.3.1 A Generic Octree Mesher
o 10.3.3.2 Some Speci c Algorithms
10.3.4 Mesh Improvement
10.4 Guaranteed-Quality Mesh Generation
Acknowledgments
Bibliography

Chapter 11 3D Delaunay Mesh Generation

11.1 Introduction
11.2 Delaunay Re nement
11.3 Termination and Output Size
11.3.1 Proof of Termination
11.3.2 Output Size
11.4 Handling Small Input Angles
11.4.1 Collar Construction
11.4.2 Protected Delaunay Re nement
11.5 Implementation and Examples
Bibliography

Chapter 12 Two-Dimensional Approaches to Sparse Matrix Partitioning

12.1 Introduction
12.2 Sparse Matrices and Hypergraphs
12.3 Parallel Sparse Matrix-Vector Multiplication
12.3.1 Using a One-Dimensional Partitioning
12.3.2 Using a Two-Dimensional Partitioning
12.4 Coarse-Grain Partitioning
12.4.1 Cartesian Partitioning and Its Variants
12.4.2 Mondriaan Partitioning by Orthogonal Recursive Bisection
12.5 Fine-Grain Partitioning
12.6 The Hybrid Partitioning Algorithm
12.7 Time Complexity
12.8 Experimental Results
12.9 Conclusions and Outlook
Acknowledgments
Bibliography

Chapter 13 Parallel Partitioning, Coloring, and Ordering in Scientific Computing

13.1 Introduction
13.2 Partitioning and Load Balancing
13.2.1 Partitioning for Mesh Computations
o 13.2.1.1 Mesh Models
o 13.2.1.2 Observations and Conclusions
13.2.2 Partitioning for Sparse Matrices
13.3 Coloring
13.3.1 Jacobians by Finite Differences
13.3.2 Preconditioning for Iterative Solvers
13.3.3 Parallel Coloring
13.4 Ordering
13.4.1 Fill-Reducing Ordering of Sparse Matrices
13.4.2 Symmetric Positive Definite Case
13.4.3 Unsymmetric Case
13.5 The Zoltan Toolkit for CSC
13.5.1 Zoltan Partitioning
13.5.2 Zoltan Coloring
13.5.3 Zoltan Matrix Ordering
13.6 Conclusions and Future Work
Bibliography

Chapter 14 Scotch and PT-Scotch Graph Partitioning Software: An Overview

14.1 Introduction
14.2 The Problems to Solve
14.2.1 Static Mapping for Parallel Processing
14.2.2 Sparse Matrix Reordering
14.3 General Architecture of the Scotch Library
14.3.1 Design Choices
14.3.2 Distributed Graph Structure
14.3.3 Library Architecture
14.4 Multilevel Framework
14.4.1 Re nement
14.4.2 Coarsening
14.4.3 Initial Partitioning
14.5 Parallel Graph Coarsening Algorithms
14.5.1 Matching
14.5.2 Folding
14.5.3 Multi-Centralization for Initial Partitioning
14.6 Parallel Partition Re nement Algorithms
14.6.1 Partition Re nement
14.6.2 Band Graphs
14.6.3 Multi-Centralization for Sequential Re nement
14.6.4 Di usion Algorithms
14.7 Performance Issues
14.8 Conclusion and Future Works
Acknowledgments
Bibliography

Chapter 15 Massively Parallel Graph Partitioning: A Case in Human Bone Simulations

15.1 Introduction
15.2 Computational Model
15.2.1 Software Implementation Environment
15.3 The Study
15.3.1 Weak Scalability Test
15.3.2 Strong Scalability Test
15.3.3 Repartitioning Scalability
o 15.3.3.1 Load Imbalance.
o 15.3.3.2 Scalability.
15.4 Conclusion
Acknowledgment
Bibliography

Chapter 16 Algorithmic and Statistical Perspectives on Large-Scale Data Analysis

16.1 Introduction
16.2 Diverse Approaches to Modern Data Analysis Problems
16.3 Genetics Applications and Novel Matrix Algorithms
16.3.1 Motivating Genetics Application
16.3.2 A Formalization of and Prior Approaches to This Problem
16.3.3 An Aside on Least Squares and Statistical Leverage
16.3.4 A Two-Stage Hybrid Algorithm for the CSSP
16.3.5 Data Applications of the CSSP Algorithm
16.3.6 Some General Thoughts on Leverage Scores and Matrix Algorithms
16.4 Internet Applications and Novel Graph Algorithms
16.4.1 Motivating Internet Application
16.4.2 A Formalization of and Prior Approaches to This Problem
16.4.3 A Novel Approach to Characterizing Network Structure
16.4.4 Community-Identification Applications of This Approach
16.4.5 Some General Thoughts on Statistical Issues and Graph Algorithms
16.5 Conclusions and Future Directions
Acknowledgments
Bibliography

Chapter 17 Computational Challenges in Emerging Combinatorial Scientific Computing Applications

17.1 Introduction
17.2 Analysis of Social and Technological Networks
17.2.1 Community Identification
17.2.2 Graph Pattern Mining and Matching
17.3 Combinatorial Problems in Computational Biology
17.3.1 Short-Read Genome Assembly
17.3.2 Phylogeny Reconstruction
17.4 Summary and Concluding Remarks
Bibliography

Chapter 18 Spectral Graph Theory

18.1 Introduction
18.2 Preliminaries
18.3 The Matrices Associated with a Graph
18.3.1 Operators on the Vertices
18.3.2 The Laplacian Quadratic Form
18.3.3 The Normalized Laplacian
18.3.4 Naming the Eigenvalues
18.4 Some Examples
18.5 The Role of the Courant-Fischer Theorem
18.5.1 Low-Rank Approximations
18.6 Elementary Facts
18.7 Spectral Graph Drawing
18.8 Algebraic Connectivity and Graph Partitioning
18.8.1 Convergence of Random Walks
18.8.2 Expander Graphs
18.8.3 Ramanujan Graphs
18.8.4 Bounding .2
18.9 Coloring and Independent Sets
18.10 Perturbation Theory and Random Graphs
18.11 Relative Spectral Graph Theory
18.12 Directed Graphs
18.13 Concluding Remarks
Bibliography

Chapter 19 Algorithms for Visualizing Large Networks

19.1 Introduction
19.2 Algorithms for Drawing Large Graphs
19.2.1 Spring-Electrical Model
o 19.2.1.1 Fast Force Approximation
o 19.2.1.2 Multilevel Approach
o 19.2.1.3 An Open Problem: More Robust Coarsening Schemes
19.2.2 Stress and Strain Models
o 19.2.2.1 Stress Model
o 19.2.2.2 Strain Model (Classical MDS)
o 19.2.2.3 MDS for Large Graphs
19.2.3 High-Dimensional Embedding
19.2.4 Hall's Algorithm
19.3 Examples of Large Graph Drawings
19.4 Conclusions
Acknowledgments
Bibliography

Index