CFD Online Logo CFD Online URL
www.cfd-online.com
[Sponsors]
Home >

Chebyshev and Fourier Spectral Methods

John P. Boyd

This book provides a very readable survery of spectral methods.

Bookcover

Format: Paperback, English, 668 pages
ISBN: 0486411834
Publisher: Dover Publications
Pub. Date: 2001
Edition: 2
Book Homepage: http://www-personal.engin.umich.edu/~jpboyd/

Edit This Book Record


 

Buy This Book From:

Amazon.com

Amazon.co.uk



Have you read this book?  Write your own Review

Write the first review of this book.


Book Description

This book provides a good introduction to spectral and pseudospectral methods that is extended to advanced topics. Many corollary topics such as coordinate transformations/mappings/geometries, maxtrix solving methods, time integration, splitting, domain decomposition, partial summation, Cardinal functions, pseudospectral and semi-lagrangian methods, and nonlinear techniques are introduced and expounded upon. The book is light on proofs in favor of a "how to implement/utilize" approach. A review of the table of contents will give a good idea of what the book entails.



Table of Contents

  Contents  
  PREFACE x
  Acknowledgments xiv
  Errata and Extended-Bibliography xvi
1 Introduction 1
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 19
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 Agnesi Rule?of?Thumb  
2.16 Boundary Layer Rule-of-Thumb  
3 Galerkin & Weighted Residual Methods 61
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 81
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 98
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 109
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 127
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 159
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 172
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 183
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 202
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 222
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 252
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 265
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 290
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 Iterations for Almost Separable PDEs  
15.13 Positive Definite and Indefinite Matrices  
15.14 Preconditioned Newton Flow  
15.15 Summary & Proverbs  
16 Coordinate Transformations 323
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 338
17.1 Introduction  
17.2 Domain Truncation  
17.2.1 Domain Truncation for Rapidly-decaying Functions  
17.2.2 Domain Truncation for Slowly-Decaying Functions  
17.2.3 Domain Truncation for Time-Dependent Wave Propagation:  
17.3 Whittaker Cardinal or "Sinc" Functions  
17.4 Hermite functions  
17.5 Semi-Infinite Interval: Laguerre Functions  
17.6 New Basis Sets via Change of Coordinate  
17.7 Rational Chebyshev Functions: TBn  
17.8 Behavioral versus Numerical Boundary Conditions  
17.9 Strategy for Slowly Decaying Functions  
17.10 Numerical Examples: Rational Chebyshev Functions  
17.11 Semi-Infinite Interval: Rational Chebyshev TLn  
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 380
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 390
18.6 Annular  
18.7 Spherical Coordinates: An Overview  
18.8 The Parity Factor 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  
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 442
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 461
20.1 Introduction  
20.2 Strategy  
20.3 Examples  
20.4 Summary and Open Problems  
21 The Tau-Method 473
21.1 Introduction  
21.2 -Approximation for a Rational Function  
21.3 Differential Equations  
21.4 Canonical Polynomials  
21.5 Nomenclature  
22 Domain Decomposition Methods 479
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 494
A A Bestiary of Basis Functions 495
A.1 Trigonometric Basis Functions: Fourier Series  
A.2 Chebyshev Polynomials: Tn(x)  
A.3 Chebyshev Polynomials of the Second Kind: Un(x)  
A.4 Legendre Polynomials: Pn(x)  
A.5 Gegenbauer Polynomials  
A.6 Hermite Polynomials: Hn(x)  
A.7 Rational Chebyshev Functions: TBn(y)  
A.8 Laguerre Polynomials: Ln(x)  
A.9 Rational Chebyshev Functions: TLn(y)  
A.10 Graphs of Convergence Domains in the Complex  
B Direct Matrix-Solvers 514
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  
  CONTENTS ix
C Newton Iteration 526
C.1 Introduction  
C.2 Examples  
C.3 Eigenvalue Problems  
C.4 Summary  
D The Continuation Method 536
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 550
F Cardinal Functions 561
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 575
  Glossary 577
  Index 586

Related Book Categories

Spectral Methods


Browse| Advanced Search| Submit A Book| Help