Chebyshev and Fourier Spectral Methods

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