Combinatorial Scientific Computing

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.

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.

Combinatorial Scientific Computing: Past Successes, Current Opportunities, Future Challenges, Bruce Hendrickson and Alex PothenIntroduction The CSC Community Current Opportunities Future ChallengesConclusions

Combinatorial Problems in Solving Linear Systems, Iain Duff and Bora UçarIntroduction Basics Direct MethodsIterative MethodsConclusions

Combinatorial Preconditioners, Sivan Toledo and Haim AvronIntroduction Symmetric Diagonally Dominant Matrices and GraphsSupport TheoryEmbeddings and Combinatorial Support BoundsCombinatorial Preconditioners

Scalable Hybrid Linear Solvers, Madan Sathe, Olaf Schenk, Bora Uçar, and Ahmed SamehIntroduction PSPIKE—A Scalable Hybrid Linear Solver Combinatorics in the Hybrid Solver PSPIKEComputational Results in PDE-Constrained OptimizationConclusion

Combinatorial Problems in Algorithmic Differentiation, Uwe Naumann and Andrea WaltherIntroduction Compression TechniquesData Flow ReversalElimination TechniquesSummary and Conclusion

Combinatorial Problems in OpenAD, Jean Utke and Uwe NaumannIntroduction Computational GraphsReversal Schemes

Getting Started with ADOL-C, Andrea Walther and Andreas GriewankIntroduction 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ächterIntroduction The Inverse Medium ProblemLarge-Scale Nonlinear Optimization and IPOPT Closed Form of Derivatives Algorithmic DifferentiationSparse Linear Algebra and PARDISONumerical Experiments

Combinatorial Aspects/Algorithms in Computational Fluid Dynamics, Rainald LöhnerSystem of Conservation Laws Grid Size Estimates Work Estimates for Different Shape-FunctionsBasic Data Structures and LoopsExample: Blast in Room Conclusions and Outlook

Unstructured Mesh Generation, Jonathan Richard ShewchukIntroduction MeshesMethods of Mesh GenerationGuaranteed-Quality Mesh Generation

3D Delaunay Mesh Generation, Klaus Gärtner, Hang Si, Alexander Rand, and Noel WalkingtonIntroduction Delaunay Refinement Termination and Output SizeHandling Small Input AnglesImplementation 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ürekIntroduction Sparse Matrices and Hypergraphs Parallel Sparse Matrix–Vector MultiplicationCoarse-Grain PartitioningFine-Grain Partitioning The Hybrid Partitioning Algorithm Time ComplexityExperimental Results Conclusions and Outlook

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

Scotch and PT-Scotch Graph Partitioning Software: An Overview, François PellegriniIntroduction The Problems to SolveGeneral Architecture of the Scotch libraryMultilevel FrameworkParallel Graph Coarsening AlgorithmsParallel Partition Refinement AlgorithmsPerformance 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. WirthIntroduction Computational Model The StudyConclusion

Algorithmic and Statistical Perspectives on Large-Scale Data Analysis, Michael W. MahoneyIntroduction Diverse Approaches to Modern Data Analysis Problems Genetics Applications and Novel Matrix AlgorithmsInternet Applications and Novel Graph AlgorithmsConclusions and Future Directions

Computational Challenges in Emerging Combinatorial Scientific Computing Applications, David A. Bader and Kamesh MadduriIntroduction Analysis of Social and Technological Networks Combinatorial Problems in Computational Biology Summary and Concluding Remarks

Spectral Graph Theory, Daniel SpielmanIntroduction Preliminaries The Matrices Associated with a GraphSome Examples The Role of the Courant-Fischer Theorem Elementary Facts Spectral Graph Drawing Algebraic Connectivity and Graph PartitioningColoring and Independent Sets Perturbation Theory and Random Graphs Relative Spectral Graph Theory Directed Graphs Concluding Remarks

Algorithms for Visualizing Large Networks, Yifan HuIntroduction Algorithms for Drawing Large GraphsExamples of Large Graph Drawings Conclusions

A Bibliography appears at the end of each chapter.