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