Skip to Content

Combinatorial Scientific Computing

Edited by Uwe Naumann, Olaf Schenk

Chapman and Hall/CRC – 2012 – 600 pages

Series: Chapman & Hall/CRC Computational Science

Purchasing Options:

  • Add to CartHardback: $93.95
    978-1-43-982735-2
    January 25th 2012

Description

Combinatorial Scientific Computing explores the latest research on creating algorithms and software tools to solve key combinatorial problems on large-scale high-performance computing architectures. It includes contributions from international researchers who are pioneers in designing software and applications for high-performance computing systems.

The book offers a state-of-the-art overview of the latest research, tool development, and applications. It focuses on load balancing and parallelization on high-performance computers, large-scale optimization, algorithmic differentiation of numerical simulation code, sparse matrix software tools, and combinatorial challenges and applications in large-scale social networks. The authors unify these seemingly disparate areas through a common set of abstractions and algorithms based on combinatorics, graphs, and hypergraphs.

Combinatorial algorithms have long played a crucial enabling role in scientific and engineering computations and their importance continues to grow with the demands of new applications and advanced architectures. By addressing current challenges in the field, this volume sets the stage for the accelerated development and deployment of fundamental enabling technologies in high-performance scientific computing.

Reviews

"This text is a deep and--as any scientist working with large datasets will tell you--much-needed treatment of an emerging field, focused specifically on large-scale computing. It is readable and practical, and covers areas that have many open problems, making it an excellent resource both for scientific researchers looking for solutions and computing researchers looking for computational and combinatoric problems to solve."

— Computing Reviews, May 2013

Contents

Combinatorial Scientific Computing: Past Successes, Current Opportunities, Future Challenges, Bruce Hendrickson and Alex Pothen

Introduction

The CSC Community

Current Opportunities

Future Challenges

Conclusions

Combinatorial Problems in Solving Linear Systems, Iain Duff and Bora Uçar

Introduction

Basics

Direct Methods

Iterative Methods

Conclusions

Combinatorial Preconditioners, Sivan Toledo and Haim Avron

Introduction

Symmetric Diagonally Dominant Matrices and Graphs

Support Theory

Embeddings and Combinatorial Support Bounds

Combinatorial Preconditioners

Scalable Hybrid Linear Solvers, Madan Sathe, Olaf Schenk, Bora Uçar, and Ahmed Sameh

Introduction

PSPIKE—A Scalable Hybrid Linear Solver

Combinatorics in the Hybrid Solver PSPIKE

Computational Results in PDE-Constrained Optimization

Conclusion

Combinatorial Problems in Algorithmic Differentiation, Uwe Naumann and Andrea Walther

Introduction

Compression Techniques

Data Flow Reversal

Elimination Techniques

Summary and Conclusion

Combinatorial Problems in OpenAD, Jean Utke and Uwe Naumann

Introduction

Computational Graphs

Reversal Schemes

Getting Started with ADOL-C, Andrea Walther and Andreas Griewank

Introduction

Preparing a Code Segment for Differentiation

Easy-to-Use Drivers

Reusing the Pre-Value Tape for Arbitrary Input Values

Suggestions for Improved Efficiency

Advance Algorithmic Differentiation in ADOL-C

Tapeless Forward Differentiation

Conclusions and Further Developments

Algorithmic Differentiation and Nonlinear Optimization for an Inverse Medium Problem, Johannes Huber, Olaf Schenk, Uwe Naumann, Ebadollah Varnik, and Andreas Wächter

Introduction

The Inverse Medium Problem

Large-Scale Nonlinear Optimization and IPOPT

Closed Form of Derivatives

Algorithmic Differentiation

Sparse Linear Algebra and PARDISO

Numerical Experiments

Combinatorial Aspects/Algorithms in Computational Fluid Dynamics, Rainald Löhner

System of Conservation Laws

Grid Size Estimates

Work Estimates for Different Shape-Functions

Basic Data Structures and Loops

Example: Blast in Room

Conclusions and Outlook

Unstructured Mesh Generation, Jonathan Richard Shewchuk

Introduction

Meshes

Methods of Mesh Generation

Guaranteed-Quality Mesh Generation

3D Delaunay Mesh Generation, Klaus Gärtner, Hang Si, Alexander Rand, and Noel Walkington

Introduction

Delaunay Refinement

Termination and Output Size

Handling Small Input Angles

Implementation and Examples

Two-Dimensional Approaches to Sparse Matrix Partitioning, Rob H. Bisseling, Bas O. Fagginger Auer, A.N. Yzelman, Tristan van Leeuwen, and ┼░mit V. Çatalyürek

Introduction

Sparse Matrices and Hypergraphs

Parallel Sparse Matrix–Vector Multiplication

Coarse-Grain Partitioning

Fine-Grain Partitioning

The Hybrid Partitioning Algorithm

Time Complexity

Experimental Results

Conclusions and Outlook

Parallel Partitioning, Ordering, and Coloring in Scientific Computing, E.G. Boman, C. Chevalier, K.D. Devine, and U.V. Catalyurek

Introduction

Partitioning and Load Balancing

Coloring

Ordering

Scotch and PT-Scotch Graph Partitioning Software: An Overview, François Pellegrini

Introduction

The Problems to Solve

General Architecture of the Scotch library

Multilevel Framework

Parallel Graph Coarsening Algorithms

Parallel Partition Refinement Algorithms

Performance Issues

Conclusion and Future Works

Massively Parallel Graph Partitioning: A Case in Human Bone Simulations, C. Bekas, A. Curioni, P. Arbenz, C. Flaig, G.H. van Lenthe, R. Müller, and A.J. Wirth

Introduction

Computational Model

The Study

Conclusion

Algorithmic and Statistical Perspectives on Large-Scale Data Analysis, Michael W. Mahoney

Introduction

Diverse Approaches to Modern Data Analysis Problems

Genetics Applications and Novel Matrix Algorithms

Internet Applications and Novel Graph Algorithms

Conclusions and Future Directions

Computational Challenges in Emerging Combinatorial Scientific Computing Applications, David A. Bader and Kamesh Madduri

Introduction

Analysis of Social and Technological Networks

Combinatorial Problems in Computational Biology

Summary and Concluding Remarks

Spectral Graph Theory, Daniel Spielman

Introduction

Preliminaries

The Matrices Associated with a Graph

Some Examples

The Role of the Courant-Fischer Theorem

Elementary Facts

Spectral Graph Drawing

Algebraic Connectivity and Graph Partitioning

Coloring and Independent Sets

Perturbation Theory and Random Graphs

Relative Spectral Graph Theory

Directed Graphs

Concluding Remarks

Algorithms for Visualizing Large Networks, Yifan Hu

Introduction

Algorithms for Drawing Large Graphs

Examples of Large Graph Drawings

Conclusions

A Bibliography appears at the end of each chapter.

Author Bio

Uwe Naumann is an associate professor of computer science at RWTH Aachen University. Dr. Naumann has published more than 80 peer-reviewed papers and chaired several workshops. His research focuses on algorithmic differentiation, combinatorial graph algorithms, high-performance scientific computing, and the application of corresponding methods to real-world problems in computational science, engineering, and finance.

Olaf Schenk is an associate professor of computer science at the University of Lugano. Dr. Schenk has published more than 70 peer-reviewed book chapters, journal articles, and conference contributions. In 2008, he received an IBM Faculty Award on Cell Processors for Biomedical Hyperthermia Applications. His research interests include algorithmic and architectural problems in computational mathematics, scientific computing, and high-performance computing.

Name: Combinatorial Scientific Computing (Hardback)Chapman and Hall/CRC 
Description: Edited by Uwe Naumann, Olaf Schenk. Combinatorial Scientific Computing explores the latest research on creating algorithms and software tools to solve key combinatorial problems on large-scale high-performance computing architectures. It includes contributions from international...
Categories: Supercomputing, Algorithms & Complexity, Combinatorics