Implementing Spectral Methods for Partial Differential Equations

Algorithms for Scientists and Engineers
1. Auflage 2009
ISBN: 978-90-481-2261-5
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 397 Seiten

Autoren/Hrsg.

Inhaltsverzeichnis

1;Preface;7
2;Contents;9
3;List of Algorithms;13
4;Approximating Functions, Derivatives and Integrals;19
4.1;Spectral Approximation;20
4.1.1;Preamble: Series Solution of PDEs;20
4.1.2;The Fourier Basis Functions and Fourier Series;21
4.1.3;Series Truncation;23
4.1.4;Modal vs. Nodal Approximation;28
4.1.5;Discrete Orthogonality and Quadrature;28
4.1.6;Fourier Interpolation;31
4.1.6.1;Direct Computation of the Fourier Interpolation;34
4.1.6.2;Error of the Fourier Interpolation;36
4.1.7;The Derivative of the Fourier Interpolant;38
4.1.8;Polynomial Basis Functions;40
4.1.8.1;The Legendre Polynomials;41
4.1.8.2;The Chebyshev Polynomials;42
4.1.9;Polynomial Series;43
4.1.10;Polynomial Series Truncation;45
4.1.10.1;Derivatives of Truncated Series;47
4.1.11;Polynomial Quadrature;48
4.1.11.1;Gauss Points:;52
4.1.11.2;Lobatto Points:;52
4.1.12;Orthogonal Polynomial Interpolation;52
4.1.13;Exercises;54
4.2;Algorithms for Periodic Functions;56
4.2.1;How to Compute the Discrete Fourier Transform;56
4.2.1.1;Fourier Transforms of Complex Sequences;57
4.2.1.2;Fourier Transforms of Real Sequences;60
4.2.1.2.1;Simultaneous Fourier Transformation of Two Real Sequences;60
4.2.1.2.2;Fourier Transformation of a Real Sequence by Even-Odd Decomposition;62
4.2.1.3;The Fourier Transform in Two Space Variables;65
4.2.2;The Real Fourier Transform;67
4.2.3;How to Evaluate the Fourier Interpolation Derivative by FFT;70
4.2.4;How to Compute Derivatives by Matrix Multiplication;71
4.2.5;Exercises;73
4.3;Algorithms for Non-Periodic Functions;75
4.3.1;How to Compute the Legendre and Chebyshev Polynomials;75
4.3.2;How to Compute the Gauss Quadrature Nodes and Weights;78
4.3.2.1;Legendre Gauss Quadrature;78
4.3.2.2;Legendre Gauss-Lobatto Quadrature;80
4.3.2.2.1;Benchmark Solution: Legendre Nodes and Weights;83
4.3.2.3;Chebyshev Gauss Quadratures;83
4.3.3;How to Evaluate Chebyshev Interpolants via the FFT;83
4.3.3.1;The Fast Chebyshev Transform;84
4.3.4;How to Evaluate Polynomial Interpolants in Lagrange Form;89
4.3.5;How to Evaluate Polynomial Derivatives;94
4.3.5.1;Direct Evaluation of the Derivative;95
4.3.5.2;Evaluation of Derivatives by Matrix Multiplication;97
4.3.5.3;Even-Odd Decomposition;98
4.3.5.4;Evaluation by Transform Methods;100
4.3.5.5;Performance of Various Polynomial Derivative Algorithms;100
4.3.6;Exercises;103
5;Approximating Solutions of PDEs;104
5.1;Survey of Spectral Approximations;105
5.1.1;The Fourier Collocation Method;108
5.1.1.1;How to Implement the Fourier Collocation Method;110
5.1.1.2;Benchmark Solution;113
5.1.2;The Fourier Galerkin Method;115
5.1.2.1;How to Implement the Fourier Galerkin Method;117
5.1.2.2;Benchmark Solution;120
5.1.3;Nonlinear and Product Terms;121
5.1.3.1;The Galerkin Approximation;121
5.1.3.2;How to Compute the Convolution Sum;123
5.1.3.3;The Collocation Approximation;126
5.1.4;Polynomial Collocation Methods;129
5.1.4.1;Approximation of the Diffusion Equation;129
5.1.4.2;How to Implement the Methods;131
5.1.4.3;Benchmark Solution;133
5.1.4.4;Approximation of Scalar Advection;134
5.1.5;The Legendre Galerkin Method;137
5.1.5.1;How to Implement the Method;141
5.1.6;The Nodal Continuous Galerkin Method;143
5.1.6.1;How to Implement the Method;147
5.1.6.2;Benchmark Solution;148
5.1.7;The Nodal Discontinuous Galerkin Method;148
5.1.7.1;How to Implement the Method;152
5.1.7.2;Benchmark Solution;157
5.1.8;Summary and Some Broad Generalizations;158
5.1.9;Exercises;159
5.2;Spectral Approximation on the Square;162
5.2.1;Approximation of Functions in Multiple Space Dimensions;162
5.2.2;Potential Problems on the Square;164
5.2.2.1;The Collocation Approximation;165
5.2.2.1.1;How to Implement the Collocation Approximation;167
5.2.2.1.2;How to Solve the Linear System;170
5.2.2.1.3;Direct Solution of the Equations;171
5.2.2.1.4;Iterative Solution of the Equations;173
5.2.2.1.5;A Finite Difference Preconditioner;175
5.2.2.1.6;How to Construct the Iterative Potential Solver;180
5.2.2.1.7;Benchmark Solution;183
5.2.2.2;The Nodal Galerkin Approximation;186
5.2.2.2.1;How to Implement the Nodal Galerkin Approximation;190
5.2.2.2.2;Direct Solution of the Equations;192
5.2.2.2.3;Iterative Solution of the Equations;192
5.2.2.2.4;A Finite Element Preconditioner;193
5.2.2.2.5;Construction of the PCG Solver;198
5.2.2.2.6;Benchmark Solution;199
5.2.3;Approximation of Time Dependent Advection-Diffusion;201
5.2.3.1;The Collocation Approximation;201
5.2.3.2;The Nodal Galerkin Approximation;202
5.2.3.3;Time Integration;204
5.2.3.4;How to Implement the Approximations;206
5.2.3.4.1;Multilevel Time Storage;206
5.2.3.4.2;The Advection-Diffusion Class;207
5.2.3.4.3;The Transport Terms;208
5.2.3.4.4;The Iterative Solver;208
5.2.3.4.5;Multistep Time Integration;212
5.2.3.5;Benchmark Solution: Advection and Diffusion of a Spot in a Uniform Flow;213
5.2.4;Approximation of Wave Propagation Problems;215
5.2.4.1;The Nodal Discontinuous Galerkin Approximation;217
5.2.4.1.1;The Boundary Flux;221
5.2.4.2;How to Implement the Nodal Discontinuous Galerkin Approximation;225
5.2.4.3;Benchmark Solution: Plane Wave Propagation;229
5.2.4.4;Benchmark Solution: Propagation of a Circular Sound Wave;230
5.2.5;Exercises;231
5.3;Transformation Methods from Square to Non-Square Geometries;235
5.3.1;Mappings and Coordinate Transformations;235
5.3.1.1;Mapping a Straight Sided Quadrilateral;236
5.3.1.2;How to Approximate Curved Boundaries;237
5.3.1.3;How to Map the Reference Square to a Curved-Sided Quadrilateral;241
5.3.2;Transformation of Equations under Mappings;243
5.3.2.1;Two-Dimensional Forms;250
5.3.3;How to Approximate the Metric Terms;252
5.3.4;How to Compute the Metric Terms;254
5.3.5;Exercises;256
5.4;Spectral Methods in Non-Square Geometries;259
5.4.1;Steady Potentials in a Quadrilateral Domain;259
5.4.1.1;The Collocation Approximation;259
5.4.1.1.1;How to Implement the Collocation Approximation;261
5.4.1.2;The Nodal Galerkin Approximation;264
5.4.1.2.1;How to Implement the Nodal Galerkin Method;265
5.4.1.3;Solution of the Linear Systems;266
5.4.1.4;Benchmark Solution: Potential in Non-Square Domains;271
5.4.1.5;Benchmark Solution: Incompressible Flow over a Circular Obstacle;273
5.4.2;Steady Potentials in an Annulus;276
5.4.2.1;Benchmark Solution: Potential in an Annulus with a Source;283
5.4.3;Advection and Diffusion in Quadrilateral Domains;284
5.4.3.1;Transformation of the Advection-Diffusion Equation;284
5.4.3.2;The Collocation Approximation;285
5.4.3.3;The Nodal Galerkin Approximation;286
5.4.3.4;How to Implement the Approximations;287
5.4.3.5;Benchmark Solution: Advection and Diffusion in a Non-Square Geometry;288
5.4.3.6;Benchmark Solution: Advection and Diffusion of a Pollutant in a Curved Channel;289
5.4.4;Conservation Laws in Quadrilateral Domains;291
5.4.4.1;The Nodal Discontinuous Galerkin Approximation;292
5.4.4.2;How to Implement the Nodal Discontinuous Galerkin Approximation;294
5.4.4.2.1;Data Storage;294
5.4.4.2.2;The MappedNodalDGClass;295
5.4.4.2.3;The Time Derivative;296
5.4.4.3;Benchmark Solution: Acoustic Scattering off a Cylinder;297
5.4.5;Exercises;301
5.5;Spectral Element Methods;305
5.5.1;Spectral Element Methods in One Space Dimension;308
5.5.1.1;The Continuous Galerkin Spectral Element Method;309
5.5.1.2;How to Implement the Continuous Galerkin Spectral Element Method;313
5.5.1.2.1;The Spectral Element Class;314
5.5.1.2.2;Global Operations;315
5.5.1.2.3;The Diffusion Approximation;316
5.5.1.2.4;Side Operators and Residual Procedures;317
5.5.1.2.5;Iterative Solver;317
5.5.1.2.6;The Time Integration Procedure;317
5.5.1.3;Benchmark Solution: Cooling of a Temperature Spot;317
5.5.1.4;The Discontinuous Galerkin Spectral Element Method;320
5.5.1.5;How to Implement the Discontinuous Galerkin Spectral Element Method;322
5.5.1.5.1;The Elements;323
5.5.1.5.2;The Mesh;325
5.5.1.5.3;Time Integration;325
5.5.1.6;Benchmark Solution: Wave Propagation and Reflection;327
5.5.2;The Two-Dimensional Mesh and Its Specification;329
5.5.2.1;How to Construct a Two-Dimensional Mesh;333
5.5.2.1.1;Nodes;333
5.5.2.1.2;Elements;334
5.5.2.1.3;Edges;335
5.5.2.1.4;The Mesh;335
5.5.2.2;Benchmark Solution: A Spectral Element Mesh for a Disk;338
5.5.3;The Spectral Element Method in Two Space Dimensions;338
5.5.3.1;How to Implement the Spectral Element Method;343
5.5.3.1.1;The Potential Class;344
5.5.3.1.2;Global Procedures;345
5.5.3.1.3;Procedures for the Iterative Solver;347
5.5.3.1.4;The Driver;349
5.5.3.2;Benchmark Solution: Steady Temperatures in a Long Cylindrical Rod;352
5.5.4;The Discontinuous Galerkin Spectral Element Method;353
5.5.4.1;How to Implement the Discontinuous Galerkin Spectral Element Method;355
5.5.4.2;Benchmark Solution: Propagation of a Circular Wave in a Circular Domain;356
5.5.4.3;Benchmark Solution: Transmission and Reflection from a Material Interface;359
5.5.5;Exercises;363
6;Pseudocode Conventions;367
6.1;Variables and Arithmetic Operations;367
6.2;Arrays;367
6.3;Functions and Other Procedures;368
6.4;Pointers;368
6.5;Object Oriented Algorithms;368
7;Floating Point Arithmetic;370
8;Basic Linear Algebra Subroutines (BLAS);372
9;Linear Solvers;374
9.1;Direct Solvers;374
9.1.1;Tri-Diagonal Solver;374
9.1.2;LU Factorization;375
9.2;Iterative Solvers;379
10;Data Structures;383
10.1;Linked Lists;383
10.1.1;Example: Elements that Share a Node;386
10.2;Hash Tables;387
10.2.1;Example: Avoiding Duplicate Edges in a Mesh;391
11;References;394
12;Index of Algorithms;395
13;Subject Index;397