CHEBYSHEV AND FOURIER SPECTRAL METHODS
CONTENTS INTRODUCTION SERIES EXPANSIONS FIRST EXAMPLE COMPARISON WITH ?NITE ELEMENT METHODS COMPARISONS WITH FINITE DIFFERENCES PARALLEL COMPUTERS CHOICE OF BASIS FUNCTIONS BOUNDARY CONDITIONS NON-INTERPOLATING AND PSEUDOSPECTRAL NONLINEARITY 1 10 TIME-DEPENDENT PROBLEMS 1 11 FAQ: FREQUENTLY ASKED QUESTIONS 1 12 THE CHRYSALIS CHEBYSHEV & FOURIER SERIES FOURIER SERIES ORDERS OF CONVERGENCE CONVERGENCE ORDER ASSUMPTION OF EQUAL ERRORS DARBOUX’S PRINCIPLE WHY TAYLOR SERIES FAIL LOCATION OF SINGULARITIES CORNER SINGULARITIES & COMPATIBILITY CONDITIONS FACE: INTEGRATION-BY-PARTS BOUND 2 10 ASYMPTOTIC CALCULATION OF FOURIER COEF?CIENTS 2 11 CONVERGENCE THEORY: CHEBYSHEV POLYNOMIALS 2 12 LAST COEF?CIENT 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 GALERKIN & WEIGHTED RESIDUAL METHODS MEAN WEIGHTED RESIDUAL METHODS COMPLETENESS AND BOUNDARY CONDITIONS INNER PRODUCT & ORTHOGONALITY GALERKIN METHOD INTEGRATION-BY-PARTS GALERKIN METHOD: CASE STUDIES SEPARATION-OF-VARIABLES & THE GALERKIN METHOD HEISENBERG MATRIX MECHANICS THE GALERKIN METHOD TODAY INTERPOLATION, COLLOCATION & ALL THAT POLYNOMIAL INTERPOLATION GAUSSIAN INTEGRATION & PSEUDOSPECTRAL GRIDS PSEUDOSPECTRAL IS GALERKIN METHOD VIA QUADRATURE PSEUDOSPECTRAL ERRORS CARDINAL FUNCTIONS WHITTAKER CARDINAL OR “SINC” FUNCTIONS TRIGONOMETRIC INTERPOLATION CARDINAL FUNCTIONS FOR ORTHOGONAL POLYNOMIALS TRANSFORMATIONS AND INTERPOLATION PSEUDOSPECTRAL METHODS FOR BVPS CHOICE OF BASIS SET BOUNDARY CONDITIONS: BEHAVIORAL & NUMERICAL “BOUNDARY-BORDERING” “BASIS RECOMBINATION” TRANS?NITE INTERPOLATION THE CARDINAL FUNCTION BASIS THE INTERPOLATION GRID 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 LINEAR EIGENVALUE PROBLEMS THE NO-BRAIN METHOD QR/QZ ALGORITHM EIGENVALUE RULE-OF-THUMB FOUR KINDS OF STURM-LIOUVILLE PROBLEMS CRITERIA FOR REJECTING EIGENVALUES “SPURIOUS” EIGENVALUES REDUCING THE CONDITION NUMBER THE POWER METHOD INVERSE POWER METHOD 7 10 COMBINING GLOBAL & LOCAL METHODS 7 11 DETOURING INTO THE COMPLEX PLANE 7 12 COMMON ERRORS SYMMETRY & PARITY PARITY MODIFYING THE GRID TO EXPLOIT PARITY OTHER DISCRETE SYMMETRIES AXISYMMETRIC & APPLE-SLICING MODELS EXPLICIT TIME-INTEGRATION METHODS SPATIALLY-VARYING COEF?CIENTS THE SHAMROCK PRINCIPLE LINEAR AND NONLINEAR EXAMPLE: KDV EQUATION 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: DE?NITION & EXAMPLES 12 9 NUMERICALLY-INDUCED SLOW MANIFOLDS 12 10INITIALIZATION 12 11THE METHOD OF MULTIPLE SCALES(BAER-TRIBBIA) 12 12NONLINEAR GALERKIN METHODS 12 13WEAKNESSES OF THE NONLINEAR GALERKIN METHOD 12 14TRACKING THE SLOW MANIFOLD 12 15THREE 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 10OFF-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 11HIGHER ORDER SL METHODS 14 12HISTORY AND RELATIONSHIPS TO OTHER METHODS 14 13SUMMARY 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 10RECURSIONS & FORMAL INTEGRATION: CONSTANT COEF?CIENT ODES 15 11DIRECT METHODS FOR SEPARABLE PDE’S 15 12FAST ITERATIONS FOR ALMOST SEPARABLE PDES 15 13POSITIVE DE?NITE AND INDE?NITE MATRICES 15 14PRECONDITIONED NEWTON FLOW 15 15SUMMARY & PROVERBS 16 COORDINATE TRANSFORMATIONS 16 1 INTRODUCTION 16 2 PROGRAMMING CHEBYSHEV METHODS 16 3 THEORY OF 1-D TRANSFORMATIONS 16 4 IN?NITE AND SEMI-IN?NITE 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 2 2 DOMAIN TRUNCATION FOR SLOWLY-DECAYING FUNCTIONS 17 2 3 DOMAIN TRUNCATION FOR TIME-DEPENDENT WAVE PROPAGATION: SPONGE LAYERS 17 3 WHITTAKER CARDINAL OR “SINC” FUNCTIONS 17 4 HERMITE FUNCTIONS 17 5 SEMI-IN?NITE 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 10NUMERICAL EXAMPLES: RATIONAL CHEBYSHEV FUNCTIONS 17 11SEMI-IN?NITE INTERVAL: RATIONAL CHEBYSHEV TLN 17 12NUMERICAL EXAMPLES: CHEBYSHEV FOR SEMI-IN?NITE INTERVAL 17 13STRATEGY: OSCILLATORY, NON-DECAYING FUNCTIONS 17 14WEIDEMAN-CLOOT SINH MAPPING 17 15SUMMARY 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 ANNULAR DOMAINS 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 10THE POLE PROBLEM: SPHERICAL COORDINATES 18 11SPHERICAL HARMONICS: INTRODUCTION 18 12LEGENDRE 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 13EQUIAREAL RESOLUTION 18 14SPHERICAL HARMONICS: LIMITED-AREA MODELS 18 15SPHERICAL HARMONICS AND PHYSICS 18 16ASYMPTOTIC APPROXIMATIONS, I 18 17ASYMPTOTIC APPROXIMATIONS, II 18 18SOFTWARE: SPHERICAL HARMONICS 18 19SEMI-IMPLICIT: SHALLOW WATER 18 20FRONTS 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 21RESOLUTION OF SPECTRAL MODELS 18 22VECTOR HARMONICS & HOUGH FUNCTIONS 18 23RADIAL/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 24STELLAR CONVECTION IN A SPHERICAL ANNULUS: GLATZMAIER (1984) 18 25NON-TENSOR GRIDS: ICOSAHEDRAL, ETC 18 26ROBERT BASIS FOR THE SPHERE 18 27PARITY-MODI?ED LATITUDINAL FOURIER SERIES 18 28PROJECTIVE FILTERING FOR LATITUDINAL FOURIER SERIES 18 29SPECTRAL ELEMENTS ON THE SPHERE 18 30SPHERICAL HARMONICS BESIEGED 18 31ELLIPTIC AND ELLIPTIC CYLINDER COORDINATES 18 32SUMMARY 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 IN?NITE 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 ?-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 IN?UENCE MATRIX METHOD 22 10TWO-DIMENSIONAL MAPPINGS & SECTORIAL ELEMENTS 22 11PROSPECTUS