Implementing Spectral Methods for Partial Differential Equations (eBook)

Algorithms for Scientists and Engineers

David A. Kopriva (Autor)

eBook Download: PDF

2009
XVIII, 397 Seiten
Springer Netherland (Verlag)
978-90-481-2261-5 (ISBN)

Infos

This book explains how to solve partial differential equations numerically using single and multidomain spectral methods. It shows how only a few fundamental algorithms form the building blocks of any spectral code, even for problems with complex geometries.

David Kopriva is Professor of Mathematics at the Florida State University, where he has taught since 1985. He is an expert in the development, implementation and application of high order spectral multi-domain methods for time dependent problems. In 1986 he developed the first multi-domain spectral method for hyperbolic systems, which was applied to the Euler equations of gas dynamics.

Inhalt

Preface 7
Contents 9
List of Algorithms 13
Approximating Functions, Derivatives and Integrals 19
Spectral Approximation 20
Preamble: Series Solution of PDEs 20
The Fourier Basis Functions and Fourier Series 21
Series Truncation 23
Modal vs. Nodal Approximation 28
Discrete Orthogonality and Quadrature 28
Fourier Interpolation 31
Direct Computation of the Fourier Interpolation 34
Error of the Fourier Interpolation 36
The Derivative of the Fourier Interpolant 38
Polynomial Basis Functions 40
The Legendre Polynomials 41
The Chebyshev Polynomials 42
Polynomial Series 43
Polynomial Series Truncation 45
Derivatives of Truncated Series 47
Polynomial Quadrature 48
Gauss Points: 52
Lobatto Points: 52
Orthogonal Polynomial Interpolation 52
Exercises 54
Algorithms for Periodic Functions 56
How to Compute the Discrete Fourier Transform 56
Fourier Transforms of Complex Sequences 57
Fourier Transforms of Real Sequences 60
Simultaneous Fourier Transformation of Two Real Sequences 60
Fourier Transformation of a Real Sequence by Even-Odd Decomposition 62
The Fourier Transform in Two Space Variables 65
The Real Fourier Transform 67
How to Evaluate the Fourier Interpolation Derivative by FFT 70
How to Compute Derivatives by Matrix Multiplication 71
Exercises 73
Algorithms for Non-Periodic Functions 75
How to Compute the Legendre and Chebyshev Polynomials 75
How to Compute the Gauss Quadrature Nodes and Weights 78
Legendre Gauss Quadrature 78
Legendre Gauss-Lobatto Quadrature 80
Benchmark Solution: Legendre Nodes and Weights 83
Chebyshev Gauss Quadratures 83
How to Evaluate Chebyshev Interpolants via the FFT 83
The Fast Chebyshev Transform 84
How to Evaluate Polynomial Interpolants in Lagrange Form 89
How to Evaluate Polynomial Derivatives 94
Direct Evaluation of the Derivative 95
Evaluation of Derivatives by Matrix Multiplication 97
Even-Odd Decomposition 98
Evaluation by Transform Methods 100
Performance of Various Polynomial Derivative Algorithms 100
Exercises 103
Approximating Solutions of PDEs 104
Survey of Spectral Approximations 105
The Fourier Collocation Method 108
How to Implement the Fourier Collocation Method 110
Benchmark Solution 113
The Fourier Galerkin Method 115
How to Implement the Fourier Galerkin Method 117
Benchmark Solution 120
Nonlinear and Product Terms 121
The Galerkin Approximation 121
How to Compute the Convolution Sum 123
The Collocation Approximation 126
Polynomial Collocation Methods 129
Approximation of the Diffusion Equation 129
How to Implement the Methods 131
Benchmark Solution 133
Approximation of Scalar Advection 134
The Legendre Galerkin Method 137
How to Implement the Method 141
The Nodal Continuous Galerkin Method 143
How to Implement the Method 147
Benchmark Solution 148
The Nodal Discontinuous Galerkin Method 148
How to Implement the Method 152
Benchmark Solution 157
Summary and Some Broad Generalizations 158
Exercises 159
Spectral Approximation on the Square 162
Approximation of Functions in Multiple Space Dimensions 162
Potential Problems on the Square 164
The Collocation Approximation 165
How to Implement the Collocation Approximation 167
How to Solve the Linear System 170
Direct Solution of the Equations 171
Iterative Solution of the Equations 173
A Finite Difference Preconditioner 175
How to Construct the Iterative Potential Solver 180
Benchmark Solution 183
The Nodal Galerkin Approximation 186
How to Implement the Nodal Galerkin Approximation 190
Direct Solution of the Equations 192
Iterative Solution of the Equations 192
A Finite Element Preconditioner 193
Construction of the PCG Solver 198
Benchmark Solution 199
Approximation of Time Dependent Advection-Diffusion 201
The Collocation Approximation 201
The Nodal Galerkin Approximation 202
Time Integration 204
How to Implement the Approximations 206
Multilevel Time Storage 206
The Advection-Diffusion Class 207
The Transport Terms 208
The Iterative Solver 208
Multistep Time Integration 212
Benchmark Solution: Advection and Diffusion of a Spot in a Uniform Flow 213
Approximation of Wave Propagation Problems 215
The Nodal Discontinuous Galerkin Approximation 217
The Boundary Flux 221
How to Implement the Nodal Discontinuous Galerkin Approximation 225
Benchmark Solution: Plane Wave Propagation 229
Benchmark Solution: Propagation of a Circular Sound Wave 230
Exercises 231
Transformation Methods from Square to Non-Square Geometries 235
Mappings and Coordinate Transformations 235
Mapping a Straight Sided Quadrilateral 236
How to Approximate Curved Boundaries 237
How to Map the Reference Square to a Curved-Sided Quadrilateral 241
Transformation of Equations under Mappings 243
Two-Dimensional Forms 250
How to Approximate the Metric Terms 252
How to Compute the Metric Terms 254
Exercises 256
Spectral Methods in Non-Square Geometries 259
Steady Potentials in a Quadrilateral Domain 259
The Collocation Approximation 259
How to Implement the Collocation Approximation 261
The Nodal Galerkin Approximation 264
How to Implement the Nodal Galerkin Method 265
Solution of the Linear Systems 266
Benchmark Solution: Potential in Non-Square Domains 271
Benchmark Solution: Incompressible Flow over a Circular Obstacle 273
Steady Potentials in an Annulus 276
Benchmark Solution: Potential in an Annulus with a Source 283
Advection and Diffusion in Quadrilateral Domains 284
Transformation of the Advection-Diffusion Equation 284
The Collocation Approximation 285
The Nodal Galerkin Approximation 286
How to Implement the Approximations 287
Benchmark Solution: Advection and Diffusion in a Non-Square Geometry 288
Benchmark Solution: Advection and Diffusion of a Pollutant in a Curved Channel 289
Conservation Laws in Quadrilateral Domains 291
The Nodal Discontinuous Galerkin Approximation 292
How to Implement the Nodal Discontinuous Galerkin Approximation 294
Data Storage 294
The MappedNodalDGClass 295
The Time Derivative 296
Benchmark Solution: Acoustic Scattering off a Cylinder 297
Exercises 301
Spectral Element Methods 305
Spectral Element Methods in One Space Dimension 308
The Continuous Galerkin Spectral Element Method 309
How to Implement the Continuous Galerkin Spectral Element Method 313
The Spectral Element Class 314
Global Operations 315
The Diffusion Approximation 316
Side Operators and Residual Procedures 317
Iterative Solver 317
The Time Integration Procedure 317
Benchmark Solution: Cooling of a Temperature Spot 317
The Discontinuous Galerkin Spectral Element Method 320
How to Implement the Discontinuous Galerkin Spectral Element Method 322
The Elements 323
The Mesh 325
Time Integration 325
Benchmark Solution: Wave Propagation and Reflection 327
The Two-Dimensional Mesh and Its Specification 329
How to Construct a Two-Dimensional Mesh 333
Nodes 333
Elements 334
Edges 335
The Mesh 335
Benchmark Solution: A Spectral Element Mesh for a Disk 338
The Spectral Element Method in Two Space Dimensions 338
How to Implement the Spectral Element Method 343
The Potential Class 344
Global Procedures 345
Procedures for the Iterative Solver 347
The Driver 349
Benchmark Solution: Steady Temperatures in a Long Cylindrical Rod 352
The Discontinuous Galerkin Spectral Element Method 353
How to Implement the Discontinuous Galerkin Spectral Element Method 355
Benchmark Solution: Propagation of a Circular Wave in a Circular Domain 356
Benchmark Solution: Transmission and Reflection from a Material Interface 359
Exercises 363
Pseudocode Conventions 367
Variables and Arithmetic Operations 367
Arrays 367
Functions and Other Procedures 368
Pointers 368
Object Oriented Algorithms 368
Floating Point Arithmetic 370
Basic Linear Algebra Subroutines (BLAS) 372
Linear Solvers 374
Direct Solvers 374
Tri-Diagonal Solver 374
LU Factorization 375
Iterative Solvers 379
Data Structures 383
Linked Lists 383
Example: Elements that Share a Node 386
Hash Tables 387
Example: Avoiding Duplicate Edges in a Mesh 391
References 394
Index of Algorithms 395
Subject Index 397

Produkt-Details

• Erscheint lt. Verlag: 27.5.2009
• Reihe/Serie: Scientific Computation
• Reihe/Serie: Scientific Computation
• Zusatzinfo: XVIII, 397 p.
• Verlagsort: Dordrecht
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Analysis
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Naturwissenschaften ► Physik / Astronomie
• Themenwelt: Technik
• Schlagworte: algorithms • Approximation of Derivatives • FFT Algorithm • Implementation of Spectral Methods • Implementing Spectral Methods • Multidomain Spectral Methods • Numerical Algorithms • Numerical Solutions of PDE • partial differential equation • Partial differential equations • PDE • PDEs in Realistic Geometries • PDEs with Complex G • PDEs with Complex Geometries • Scientific Computing • Solving Complex PDEs • Spectral Approximations of PDEs • spectral method
• ISBN-10: 90-481-2261-9 / 9048122619
• ISBN-13: 978-90-481-2261-5 / 9789048122615