Kopriva 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

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.

Autoren/Hrsg.

Kopriva, David

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