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.
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 Hybri 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...