Generic Software Components for Scientific Computing

Introduction......Page 7 An Algorithm-centered Approach to Software......Page 13 Fundamental Issues......Page 14 Algorithmic Complexity......Page 16 Efficiency Driven Complexity......Page 17 User Interaction Complexity......Page 18 The Central Role of Grids for Numerical PDE Solution......Page 19 What Are Components?......Page 20 Quality Criteria for Scientific Computing Components......Page 21 Review of Components for Scientific Computing......Page 26 Shortcomings of Scientific Computing Components......Page 29 Reuse Case Study: Sparse System Solver......Page 30 Data Structure Variance in Scientific Computing......Page 33 Reuse of Algorithms and Data Structure Conversions......Page 34 The Idea of Generic Programming......Page 35 An Introductory Example: The STL......Page 38 Sparse matrices revisited......Page 41 Generic Programming for Grids......Page 42 Language and Implementation Issues......Page 43 Related Work......Page 45 Mathematical properties of grids......Page 47 Topology of Cellular Systems......Page 48 Convex Polytopes......Page 53 Combinatorial Structure of Complexes......Page 54 Geometric Realizations of Abstract Complexes......Page 57 Some Special Grids and Geometries......Page 59 Grid Algorithm Requirements......Page 60 Persistent Storage of Grids......Page 61 Cell Neighbor Search......Page 62 Bandwidth-reducing Ordering of Grid Elements......Page 63 Graphical Output......Page 65 Particle Tracing......Page 66 Finite Volume Flux Calculation......Page 68 Finite Element Matrix Assembly......Page 70 Summary of Requirements......Page 71 Combinatorial Variabilities......Page 75 Data Association Variabilities......Page 77 Geometric Variabilities......Page 78 Review of Grid Data Structures......Page 80 Discussion......Page 82 What Belongs into a Micro-kernel?......Page 85 Grids, Elements and Handles......Page 87 Incidence Queries......Page 90 Incidence Sequences and Iterators......Page 91 An Alternative: The switch Operator......Page 92 Grid Functions......Page 93 Grid Geometries......Page 94 Grid Creation, Copy and Modification......Page 95 Examples of Concrete Grid Kernel Components......Page 96 Serialized-grid Adapters......Page 97 Implicit Grids......Page 98 Element-ranges and Subgrids......Page 99 Sequence Iterators......Page 101 Incidence Iterators......Page 102 Closure Iterators......Page 103 Boundary Iterators......Page 104 Container Grid Functions......Page 105 Generic Algorithms......Page 107 Introduction......Page 109 Machines and Models for Parallel Computing......Page 111 Geometric Partitioning for Parallel PDE Solution......Page 112 Software Support for Parallel PDE Solution......Page 115 Introduction......Page 117 Distributed Grids and Overlap Structures......Page 118 The Quotient Grid......Page 122 Stencils of Algorithms......Page 124 Distributed Grid Functions......Page 130 Distributed Overlapping Grids --- Algorithms......Page 132 Static Communication......Page 133 Determination of Hulls Generated by a Stencil......Page 134 Construction of Overlapping Grids......Page 135 Determination of the Quotient Grid......Page 139 Dynamic Grid Migration......Page 141 Overlap Representation......Page 142 Overlapping grids / grid functions......Page 144 Distributed grids / grid functions......Page 145 The Data Transfer Layer......Page 146 Algorithmic Components......Page 147 Introduction......Page 151 The Mathematical Problem......Page 152 The Finite Volume Idea......Page 154 First Order Upwind Discretization by Flux Vector Splitting......Page 155 Second Order Method by Recovery and Limiting......Page 157 A Program Family for Solution of Hyperbolic Equations......Page 158 Components Representing the Mathematical Problem......Page 159 Parallelization......Page 160 User Interaction......Page 161 The FEM approach......Page 163 A Multigrid Algorithm......Page 164 Components for Multigrid Methods......Page 165 The Need for Dealing with Existing Code......Page 168 The Parallelization......Page 169 Some General Considerations......Page 171 Benchmark A: Calculating Vertex-Cell Incidences......Page 172 Benchmark C: Facet Normal Calculation......Page 174 Final Remarks......Page 176 Summary......Page 177 Discussion......Page 178 Use and Reuse of Generic Components......Page 179 Implementing Generic Components and Applications......Page 181 Parallel Computing with Generic Components......Page 183 Outlook......Page 185 Grid Entity Concept......Page 203 Grid Vertex Concept......Page 205 Grid Sequence Iterator Concept......Page 207 Grid Incidence Iterator Concept......Page 208 Vertex-On-Cell (-Facet, ...) Iterator Concept......Page 209 Grid Range Concept......Page 210 Vertex (Edge, Cell, ...) Grid Range Concept......Page 212 Grid Concept......Page 213 Grid Element Function Concept......Page 214 Grid Function Concept......Page 215 Container Grid Function Concept......Page 216 Total Grid Function Concept......Page 217 Partial Grid Function Concept......Page 218 Triang2D......Page 219 A file adapter component......Page 220 Cell-neighbor-search Algorithm implementation......Page 224 FacetIterator component......Page 228 The CopyGrid primitive......Page 230 Code for the vertex-cell incidence benchmark......Page 233 Code for the facet normal benchmark......Page 235