Naumann / Schenk Combinatorial Scientific Computing

1. Auflage 2012
ISBN: 978-1-4398-2736-9
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 600 Seiten

Reihe: Chapman & Hall/CRC Computational Science

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.

Zielgruppe

Researchers and graduate students in high-performance computing and computational science.

Autoren/Hrsg.

Naumann, Uwe

Schenk, Olaf

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Theoretische Informatik
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik

Inhaltsverzeichnis

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

Über Autor(innen)

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.