Chebyshev and Fourier Spectral Methods: Second Revised Edition

by John P. Boyd

Overview

Completely revised text focuses on use of spectral methods to solve boundary value, eigenvalue, and time-dependent problems, but also covers Hermite, Laguerre, rational Chebyshev, sinc, and spherical harmonic functions, as well as cardinal functions, linear eigenvalue problems, matrix-solving methods, coordinate transformations, methods for unbounded intervals, spherical and cylindrical geometry, and much more. 7 Appendices. Glossary. Bibliography. Index. Over 160 text figures.

Product Details

ISBN-13:	9780486411835
Publisher:	Dover Publications
Publication date:	12/03/2001
Series:	Dover Books on Mathematics
Edition description:	Second Edition, Revised
Pages:	688
Product dimensions:	6.14(w) x 9.21(h) x (d)

Table of Contents

Preface; Acknowledgments; Errata and Extended-Bibliography
1. Introduction
1.1 Series expansions
1.2 First example
1.3 Comparison with finite element methods
1.4 Comparisons with finite differences
1.5 Parallel computers
1.6 Choice of basis functions
1.7 Boundary conditions
1.8 Non-Interpolating and Pseudospectral
1.9 Nonlinearity
1.10 Time-dependent problems
1.11 FAQ: frequently asked questions
1.12 The chrysalis
2. Chebyshev & Fourier series
2.1 Introduction
2.2 Fourier series
2.3 Orders of convergence
2.4 Convergence order
2.5 Assumption of equal errors
2.6 Darboux's principle
2.7 Why Taylor series fail
2.8 Location of singularities
2.8.1 Corner singularities & compatibility conditions
2.9 FACE: Integration-by-Parts bound
2.10 Asymptotic calculation of Fourier coefficients
2.11 Convergence theory: Chebyshev polynomials
2.12 Last coefficient rule-of-thumb
2.13 Convergence theory for Legendre polynomials
2.14 Quasi-Sinusoidal rule of thumb
2.15 Witch of Agensi rule-of-thumb
2.16 Boundary layer rule-of-thumb
3. Galerkin & Weighted residual methods
3.1 Mean weighted residual methods
3.2 Completeness and boundary conditions
3.3 Inner product & orthogonality
3.4 Galerkin method
3.5 Integration-by-Parts
3.6 Galerkin method: case studies
3.7 Separation-of-Variables & the Galerkin method
3.8 Heisenberg Matrix mechanics
3.9 The Galerkin method today
4. Interpolation, collocation & all that
4.1 Introduction
4.2 Polynomial interpolation
4.3 Gaussian integration & pseudospectral grids
4.4 Pseudospectral Is Galerkin method via Quadrature
4.5 Pseudospectral errors
5. Cardinal functions
5.1 Introduction
5.2 Whittaker cardinal or "sinc" functions
5.3 Trigonometric interpolation
5.4 Cardinal functions for orthogonal polynomials
5.5 Transformations and interpolation
6. Pseudospectral methods for BVPs
6.1 Introduction
6.2 Choice of basis set
6.3 Boundary conditions: behavioral & numerical
6.4 "Boundary-bordering"
6.5 "Basis Recombination"
6.6 Transfinite interpolation
6.7 The Cardinal function basis
6.8 The interpolation grid
6.9 Computing basis functions & derivatives
6.10 Higher dimensions: indexing
6.11 Higher dimensions
6.12 Corner singularities
6.13 Matrix methods
6.14 Checking
6.15 Summary
7. Linear eigenvalue problems
7.1 The No-brain method
7.2 QR/QZ Algorithm
7.3 Eigenvalue rule-of-thumb
7.4 Four kinds of Sturm-Liouville problems
7.5 Criteria for Rejecting eigenvalues
7.6 "Spurious" eigenvalues
7.7 Reducing the condition number
7.8 The power method
7.9 Inverse power method
7.10 Combining global & local methods
7.11 Detouring into the complex plane
7.12 Common errors
8. Symmetry & parity
8.1 Introduction
8.2 Parity
8.3 Modifying the Grid to Exploit parity
8.4 Other discrete symmetries
8.5 Axisymmetric & apple-slicing models
9. Explicit time-integration methods
9.1 Introduction
9.2 Spatially-varying coefficients
9.3 The Shamrock principle
9.4 Linear and nonlinear
9.5 Example: KdV equation
9.6 Implicitly-Implicit: RLW & QG
10. Partial summation, the FFT and MMT
10.1 Introduction
10.2 Partial summation
10.3 The fast Fourier transform: theory
10.4 Matrix multiplication transform
10.5 Costs of the fast Fourier transform
10.6 Generalized FFTs and multipole methods
10.7 Off-grid interpolation
10.8 Fast Fourier transform: practical matters
10.9 Summary
11. Aliasing, spectral blocking, & blow-up
11.1 Introduction
11.2 Aliasing and Equality-on-the-grid
11.3 "2 h-Waves" and spectral blocking
11.4 Aliasing instability: history and remedies
11.5 Dealiasing and the Orszag two-thirds rule
11.6 Energy-conserving: constrained interpolation
11.7 Energy-conserving schemes: discussion
11.8 Aliasing instability: theory
11.9 Summary
12. Implicit schemes & the slow manifold
12.1 Introduction
12.2 Dispersion and amplitude errors
12.3 Errors & CFL limit for explicit schemes
12.4 Implicit time-marching algorithms
12.5 Semi-implicit methods
12.6 Speed-reduction rule-of-thumb
12.7 Slow manifold: meteorology
12.8 Slow manifold: definition & examples
12.9 Numerically-induced slow manifolds
12.10 Initialization
12.11 The method of multiple scales (Baer-Tribbia)
12.12 Nonlinear Galerkin methods
12.13 Weaknesses of the nonlinear Galerkin method
12.14 Tracking the slow manifold
12.15 Three parts to multiple scale algorithms
13. Splitting & its cousins
13.1 Introduction
13.2 Fractional steps for diffusion
13.3 Pitfalls in splitting, I: boundary conditions
13.4 Pitfalls in splitting, II: consistency
13.5 Operator theory of time-stepping
13.6 High order splitting
13.7 Splitting and fluid mechanics
14. Semi-Lagrangian advection
14.1 Concept of an integrating factor
14.2 Misuse of integrating factor methods
14.3 Semi-Lagrangian advection: introduction
14.4 Advection & method of characteristics
14.5 Three-level, 2D order semi-implicit
14.6 Multiply-upstream SL
14.7 Numerical illustrations & superconvergence
14.8 Two-level SL/SI algorithms
14.9 Noninterpolating SL & numerical diffusion
14.10 Off-grid interpolation
14.10.1 Off-grid interpolation: generalities
14.10.2 Spectral off-grid
14.10.3 Low-order polynomial interpolation
14.10.4 McGregor's Taylor series scheme
14.11 Higher order SL methods
14.12 History and relationships to other methods
14.13 Summary
15. Matrix-solving methods
15.1 Introduction
15.2 Stationary one-step iterations
15.3 Preconditioning: finite difference
15.4 Computing iterates: FFT/matrix multiplication
15.5 Alternative preconditioners
15.6 Raising the order through preconditioning
15.7 Multigrid: an overview
15.8 MRR method
15.9 Delves-Freeman block-and-diagonal iteration
15.10 Recursions & formal integration: constant coefficient ODEs
15.11 Direct methods for separable PDE's
15.12 Fast interations for almost separable PDEs
15.13 Positive definite and indefinite matrices
15.14 Preconditioned Newton flow
15.15 Summary & proverbs
16. Coordinate transformations
16.1 Introduction
16.2 Programming Chebyshev methods
16.3 Theory of 1-D transformations
16.4 Infinite and semi-infinite intervals
16.5 Maps for endpoint & corner singularities
16.6 Two-dimensional maps & corner branch points
16.7 Periodic problems & the Arctan/Tan map
16.8 Adaptive methods
16.9 Almost-equispaced Kosloff/Tal-Ezer grid
17. Methods for unbounded intervals
17.1 Introduction
17.2 Domain truncation
17.2.1 Domain truncation for rapidly-decaying functions
 
17.7 Rational Chebyshev functions: TB subscript n
17.8 Behavioral versus numerical boundary conditions
17.9 Strategy for slowly decaying functions
17.10 Numerical exemples: rational Chebyshev functions
17.11 Semi-infinite interval: rational Chebyshev TL subscript n
17.12 Numerical Examples: Chebyshev for semi-infinite interval
17.13 Strategy: Oscillatory, non-decaying functions
17.14 Weideman-Cloot Sinh mapping
17.15 Summary
18. Spherical & Cylindrical geometry
18.1 Introduction
18.2 Polar, cylindrical, toroidal, spherical
18.3 Apparent singularity at the pole
18.4 Polar coordinates: parity theorem
18.5 Radial basis sets and radial grids
18.5.1 One-sided Jacobi basis for the radial coordinate
18.5.2 Boundary value & eigenvalue problems on a disk
18.5.3 Unbounded domains including the origin in Cylindrical coordinates
18.6 Annual domains
18.7 Spherical coordinates: an overview
18.8 The parity factoro for scalars: sphere versus torus
18.9 Parity II: Horizontal velocities & other vector components
18.10 The Pole problem: spherical coordinates
18.11 Spherical harmonics: introduction
18.12 Legendre transforms and other sorrows
18.12.1 FFT in longitude/MMT in latitude
18.12.2 Substitutes and accelerators for the MMT
18.12.3 Parity and Legendre Transforms
18.12.4 Hurrah for matrix/vector multiplication
18.12.5 Reduced grid and other tricks
18.12.6 Schuster-Dilts triangular matrix acceleration
18.12.7 Generalized FFT: multipoles and all that
18.12.8 Summary
18.13 Equiareal resolution
18.14 Spherical harmonics: limited-area models
18.15 Spherical harmonics and physics
18.16 Asymptotic approximations, I
18.17 Asymptotic approximations, II
18.18 Software: spherical harmonics
18.19 Semi-implicit: shallow water
18.20 Fronts and topography: smoothing/filters
18.20.1 Fronts and topography
18.20.2 Mechanics of filtering
18.20.3 Spherical splines
18.20.4 Filter order
18.20.5 Filtering with spatially-variable order
18.20.6 Topographic filtering in meteorology
18.21 Resolution of spectral models
18.22 Vector harmonics & Hough functions
18.23 Radial/vertical coordinate: spectral or non-spectral?
18.23.1 Basis for Axial coordinate in cylindrical coordinates
18.23.2 Axial basis in toroidal coordinates
18.23.3 Vertical/radial basis in spherical coordinates
18.24 Stellar convection in a spherical annulus: Glatzmaier (1984)
18.25 Non-tensor grids: icosahedral, etc.
18.26 Robert basis for the sphere
18.27 Parity-modified latitudinal Fourier series
18.28 Projective filtering for latitudinal Fourier series
18.29 Spectral elements on the sphere
18.30 Spherical harmonics besieged
18.31 Elliptic and elliptic cylinder coordinates
18.32 Summary
19. Special tricks
19.1 Introduction
19.2 Sideband truncation
19.3 Special basis functions, I: corner singularities
19.4 Special basis functions, II: wave scattering
19.5 Weakly nonlocal solitary waves
19.6 Root-finding by Chebyshev polynomials
19.7 Hilbert transform
19.8 Spectrally-accurate quadrature methods
19.8.1 Introduction: Gaussian and Clenshaw-Curtis quadrature
19.8.2 Clenshaw-Curtis adaptivity
19.8.3 Mechanics
19.8.4 Integration of periodic functions and the trapezoidal rule
19.8.5 Infinite intervals and the trapezoidal rule
19.8.6 Singular integrands
19.8.7 Sets and solitaries
20. Symbolic calculations
20.1 Introduction
20.2 Strategy
20.3 Examples
20.4 Summary and open problems
21. The Tau-method
21.1 Introduction
21.2 tau-Approximation for a rational function
21.3 Differential equations
21.4 Canonical polynomials
21.5 Nomenclature
22. Domain decomposition methods
22.1 Introduction
22.2 Notation
22.3 Connecting the subdomains: patching
22.4 Weak coupling of elemental solutions
22.5 Variational principles
22.6 Choice of basis & grid
22.7 Patching versus variational formalism
22.8 Matrix inversion
22.9 The influence matrix method
22.10 Two-dimensional mappings & sectorial elements
22.11 Prospectus
23. Books and reviews
A. A bestiary of basis functions
A.1 Trigonometric basis functions: Fourier series
A.2 Chebyshev polynomials T subscript n (x)
A.3 Chebyshev polynomials of the second kind: U subscript n (x)
A.4 Legendre polynomials: P subscript n (x)
A.5 Gegenbauer polynomials
A.6 Hermite polynomials: H subscript n (x)
A.7 Rational Chebyshev functions: TB subscript n (y)
A.8 Laguerre polynomials: L subscript n (x)
A.9 Rational Chebyshev functions: TL subscript n (y)
A.10 Graphs of convergence domains in the complex plane
B. Direct matrix-solvers
B.1 Matrix factorizations
B.2 Banded matrix
B.3 Matrix-of-matrices theorem
B.4 Block-banded elimination: the "Lindzen-Kuo" algorithm
B.5 Block and "bordered" matrices
B.6 Cyclic banded matrices (periodic boundary conditions)
B.7 Parting shots
C. Newton iteration
C.1 Introduction
C.2 Examples
C.3 Eigenvalue problems
C.4 Summary
D. The continuation method
D.1 Introduction
D.2 Examples
D.3 Initialization strategies
D.4 Limit Points
D.5 Bifurcation points
D.6 Pseudoarclength continuation
E. Change-of-Coordinate derivative transformations
F. Cardinal functions
F.1 Introduction
F.2 General Fourier series: endpoint grid
F.3 Fourier Cosine series: endpoint grid
F.4 Fourier Sine series: endpoint grid
F.5 Cosine cardinal functions: interior grid
F.6 Sine cardinal functions: interior grid
F.7 Sinc(x): Whittaker cardinal function
F.8 Chebyshev Gauss-Lobatto ("endpoints")
F.9 Chebyshev polynomials: interior or "roots" grid
F.10 Legendre polynomials: Gauss-Lobatto grid
G. Transformation of derivative boundary conditions
Glossary; Index; References