Sparse Grids and Applications - Munich 2012

Preface......Page 6
Contents......Page 8
Efficient Pseudorecursive Evaluation Schemes for Non-adaptive Sparse Grids......Page 10
 1 Introduction......Page 11
 2 Related Work......Page 12
  3.1 The Piecewise Linear Hat Function Basis......Page 14
  3.4 Sparse Grid Evaluation......Page 16
  4.1 Common Data Structures for Hierarchical Bases......Page 17
  4.2 A Recursive Data Layout......Page 18
  5.1 Data Access Patterns......Page 20
  5.2 A Recursive Algorithm......Page 22
  5.4 Efficient Calculation of the Tensor Product......Page 23
  5.5 A Pseudorecursive Variant for GPUs......Page 25
   5.5.1 Optimizing Storage Consumption......Page 26
   5.5.2 Coalesced Memory Access......Page 27
 6 Results......Page 28
  6.1 Comparison with a Hash-Map-Based Data Structure......Page 29
   6.2.1 Memory Access......Page 30
   6.2.3 The Piecewise Polynomial Function Basis......Page 32
   6.2.4 The Extended Linear Basis with Boundary Functions......Page 33
 7 Conclusions......Page 34
 References......Page 35
 1 Introduction......Page 37
 2 The Parametric Variational Problem......Page 38
  2.2 The Parametric Elliptic Problem in Mixed Variational Form......Page 39
 3 Analytic Dependence on the Parameter......Page 41
 4 Sparse Grid Collocation......Page 46
 5 Numerical Example......Page 52
  A Simple Groundwater Flow Model......Page 53
  Solution and Convergence......Page 54
  Influence of the Parameter Dimension M......Page 56
 Appendix......Page 57
 References......Page 60
 1 Introduction......Page 62
 2 Operator Equations......Page 64
 3 Approximation on the Individual Subdomains......Page 66
 4 Generalized Sparse Tensor Product Spaces......Page 67
 5 Combination Technique......Page 69
 6 Proof of Convergence......Page 71
 7 Numerical Results......Page 75
 References......Page 80
 1 Introduction......Page 82
  2.1 Fourier Basis Representation......Page 86
  2.2 One-Dimensional Hierarchical Fourier Basis Representation......Page 88
  2.3 Generalized Sparse Grids......Page 91
  3.1 Periodic Sobolev Spaces......Page 95
  3.2 Best Linear Approximation Error......Page 97
  3.3 Approximation Error of Interpolant......Page 99
  3.4 Convergence Rates with Respect to the Cost......Page 102
  3.5 Further Generalizations of Sparse Grids......Page 103
   3.5.2 Dimension-Adaptive Approach......Page 104
 4 Numerical Experiments and Results......Page 105
 Appendix......Page 109
 References......Page 112
 1 Introduction......Page 115
  2.1 Classical Gaussian Quadrature......Page 117
  2.2 Generalized Gaussian Quadrature......Page 119
  2.3 A Certain Class of Singular Tschebyscheff-Systems......Page 121
  2.4 Examples......Page 123
   2.4.1 Powers of Logarithms......Page 124
   2.4.2 Powers of Inverse Hyperbolic Functions......Page 125
   2.4.3 Powers of the Inverse Error Function......Page 126
  3.1 Classical Construction......Page 127
  3.3 Dimension-Adaptive Sparse Grids......Page 128
  3.4 Degree of Exactness......Page 129
  4.1 Univariate Results......Page 130
  4.2 Multivariate Results for Standard Test Cases......Page 133
  4.3 Computing Multivariate Normal Probabilities by the Genz-Algorithm......Page 135
 References......Page 140
An Adaptive Wavelet Stochastic Collocation Method for Irregular Solutions of Partial Differential Equations with Random Input Data......Page 143
 1 Introduction......Page 144
 2 Problem Setting......Page 146
  2.1 Finite Dimensional Noise......Page 148
 3 Adaptive Stochastic Collocation Methods......Page 151
  3.1 Lagrange Interpolation in the Probabilistic Domain......Page 152
  3.2 Adaptive Global Sparse-Grid Lagrange Interpolation......Page 153
  3.3 Adaptive Hierarchical Sparse-Grid Lagrange Interpolation......Page 154
 4 Adaptive Wavelet Stochastic Collocation Method......Page 160
  4.1 Second-Generation Wavelets and the Lifting Scheme......Page 161
  5.1 Approximation of Irregular Deterministic Functions......Page 163
  5.2 Burgers Equation with Random Inputs......Page 165
  5.3 Elliptic PDE with Random Inputs......Page 170
 6 Conclusions......Page 173
 References......Page 174
 Introduction......Page 177
 1 The Combination Technique......Page 178
  1.1 Truncated Approximations......Page 180
  1.2 Combining in the Event of Faults......Page 183
  1.3 Results for Combinations When Faults Occur......Page 189
 2 Richardson Extrapolation and Related Ideas......Page 191
  2.1 Multivariate Richardson Extrapolation......Page 192
  2.2 Fault-Tolerant Multivariate Extrapolation......Page 194
  2.3 Results for Extrapolation......Page 195
  3.1 For a Standard Case (No Faults)......Page 196
  3.2 Fault-Tolerant Approach......Page 197
 References......Page 199
 1 Introduction......Page 200
  1.1 Algorithmic Background......Page 202
  1.2 Related Work......Page 203
  2.1  One-Dimensional Tree Structure......Page 204
  2.2  Higher Dimensional Case......Page 206
  3.1  Data Layout......Page 207
   3.1.2  Higher Dimensional Layout......Page 208
  3.2  Numerical Work: Hierarchize All Poles......Page 209
  3.4 Considerations of an Implementation......Page 210
  4.2 The Number of Grid Points v(d,)......Page 212
   4.3.2  depos: The BFS-Vector from a Position......Page 213
   4.3.3  increment: The Next BFS-Vector in the Layout......Page 214
   4.3.5 Performance Limitations of the Full Representation......Page 215
  4.4 Sparse Implementation......Page 216
  5.1 Experimental Setup......Page 217
   5.2.2 Running Times......Page 218
   5.2.3 Memory Footprint......Page 219
   5.2.4 Solvable Problem Sizes......Page 220
   5.2.5 Relation Between Preprocessing and Hierarchization......Page 221
 References......Page 223
Alternating Direction Method of Multipliers for Hierarchical Basis Approximators......Page 225
 1 Introduction......Page 226
 2 Theoretical Background......Page 227
 3 Results......Page 232
 4 Conclusions......Page 240
 References......Page 241
 1 Introduction......Page 243
  1.1 The Linear Gyrokinetic Eigenvalue Problem......Page 244
  1.2 The Combination Technique......Page 246
   1.2.2 OptiCom......Page 247
  2.1 Reformulation of the OptiCom......Page 248
  2.2 The Method of Osborne......Page 250
  2.3 Combining Both Approaches......Page 251
  2.4 Computational Effort......Page 252
 3 First Results: Analytic Example......Page 253
 4 Summary......Page 256
 References......Page 257
Classification with Probability Density Estimation on Sparse Grids......Page 258
 1 Introduction......Page 259
 3 Classification with Sparse Grid Regression......Page 261
 4 Density Estimation with Sparse Grids......Page 263
 5 Classification with Sparse Grid Density Estimation......Page 264
 6 An Offline/Online Splitting for Classification......Page 266
 7 Examples with Artificial and Real-World Data Sets......Page 268
 8 Conclusions......Page 271
 References......Page 272
 1 Introduction......Page 274
 2 Problem Formulation......Page 276
 3 Stochastic Collocation on Sparse Grids......Page 278
 4 Stochastic Adjoint Error Estimation......Page 280
  4.1 From Deterministic to Stochastic Adjoint Error Estimation......Page 281
  4.2 Discussion About Deterministic and Stochastic Errors......Page 284
  4.3 Application of Reduced Order Models......Page 285
  5.1 Elliptic Problem: Stationary Diffusion Equation......Page 286
  5.2 Parabolic Problem: Heat Equation......Page 289
 6 Conclusions......Page 293
 References......Page 294
 1 Introduction and Problem Formulation......Page 297
  2.1 Karhunen-Loève Expansion......Page 299
  2.2 Stochastic Collocation......Page 300
  2.3 Finite Element Discretization......Page 302
  3.1 Proper Orthogonal Decomposition......Page 304
  3.2 Reduced-Order Approximation of the Velocity Field......Page 305
  3.3 Reduced-Order Approximation of the Temperature Field......Page 306
  3.4 POD-Galerkin Reduced-Order Model......Page 307
  3.5 Application to Stochastic Collocation......Page 308
  4.1 Approximation of the Nusselt Number......Page 309
  4.2 Probability Density......Page 312
  4.3 Mean and Variance......Page 313
 References......Page 315
 1 Introduction......Page 318
  2.1 Theoretical Formulation......Page 319
  2.2 Implementation......Page 320
  2.3 Minimisation as Bregman Projection......Page 321
  2.4 Numerical Examples......Page 322
 3 The Classical Combination Technique......Page 325
  3.1 Numerical Examples......Page 326
  4.1 The Idea of Opticom......Page 327
  4.2 Opticom for Minimisation Problems......Page 328
  4.3 Numerical Examples......Page 329
  4.4 Opticom for General Problems......Page 330
 5 An Iterative Combination Technique......Page 331
  5.1 The Method of Combistep......Page 332
  5.2 Numerical Examples......Page 333
 6 Conclusion: Applications and Further Research......Page 335
 References......Page 336