Chebyshev and Fourier Spectral Methods

A textbook for a graduate course on solving differential equations for students in a wide range of scientific disciplines who have completed an elementary course in computer methods and have been exposed to Fourier series and complex variables at the undergraduate level. The first edition was published in 1969 by Springer-Verlag in its series Lecture Notes in Engineering. There is no index.
Annotation c. Book News, Inc., Portland, OR (booknews.com)

  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 and 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 and 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 and Weighted residual methods

  3.1 Mean weighted residual methods

  3.2 Completeness and boundary conditions

  3.3 Inner product and orthogonality

  3.4 Galerkin method

  3.5 Integration-by-Parts

  3.6 Galerkin method: case studies

  3.7 Separation-of-Variables and the Galerkin method

  3.8 Heisenberg Matrix mechanics

  3.9 The Galerkin method today

4. Interpolation, collocation and all that

  4.1 Introduction

  4.2 Polynomial interpolation

  4.3 Gaussian integration and 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 and 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 and 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 and local methods

  7.11 Detouring into the complex plane

  7.12 Common errors

8. Symmetry and parity

  8.1 Introduction

  8.2 Parity

  8.3 Modifying the Grid to Exploit parity

  8.4 Other discrete symmetries

  8.5 Axisymmetric and 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 and 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, and 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 and the slow manifold

  12.1 Introduction

  12.2 Dispersion and amplitude errors

  12.3 Errors and 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 and 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 and 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 and method of characteristics

  14.5 Three-level, 2D order semi-implicit

  14.6 Multiply-upstream SL

  14.7 Numerical illustrations and superconvergence

  14.8 Two-level SL/SI algorithms

  14.9 Noninterpolating SL and 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 and 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 and 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 and corner singularities

  16.6 Two-dimensional maps and corner branch points

  16.7 Periodic problems and 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 and 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 and 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 and 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 and 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 and grid

  22.7 Patching versus variational formalism

  22.8 Matrix inversion

  22.9 The influence matrix method

  22.10 Two-dimensional mappings and 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