element boundaries.

h-p FINITE ELEMENT: See SPECTRAL ELEMENT.

IMBRICATE SERIES: An in¬nite series for a spatially periodic function which is the su-

perposition of an in¬nite number of evenly spaced identical copies of a “pattern”

function A(x). It may be shown that all periodic functions have imbricate series in

addition to their Fourier expansions, and often the imbricate series converge faster.

Imbricate series may be generalized to an arbitrary number of dimensions.

IMPLICIT (TIME-MARCHING): A time-integration scheme in which it is necessary to

solve a boundary-value problem to compute the solution at the new time level. The

Crank-Nicholson method is an example. (Chap. 12.)

IMPLICITLY-IMPLICIT: A label for a time-dependent partial differential equation in which

the time derivative is multiplied by a differential operator L so that it is necessary to

solve a boundary value problem at every time step even to apply an explicit time-

marching scheme. (Chap. 9.)

INFINITE ORDER CONVERGENCE: A spectral series possesses the property of “in¬-

nite order convergence” if the error decreases faster than any ¬nite inverse power

of N as N , the number of terms in the truncated series, increases. A synonym for

“exponential convergence”.

INTERPOLANT: An approximation PN ’1 (x) whose free parameters or coef¬cients are

chosen by the requirement that

f (xi ) = PN ’1 (xi ) i = 1, . . . , N

at a set of N grid points. The process of computing such an approximation is INTER-

POLATION.

Glossary

582

ISOLA: For a nonlinear equation that depends upon two parameters, ± and „ , an “isola”

is a one-parameter family of solutions, parameterized by some quantity s, such that

(±(s), „ (s)) is a simple closed curve in the ±’„ plane. (From Latin “insula”, “island”,

through Italian “isolato”, “isolate”.)

JURY PROBLEM: Numerical slang for a boundary value problem in one or more dimen-

sions. The reason for the name is that when discretized by any reasonable difference

or spectral scheme, the solution must be computed on the entire grid simultaneously.

All the boundary and interior values render a “verdict” on the solution at each point.

See also MARCHING PROBLEM.

LANCZOS-TAU METHOD: Technique for solving differential equations which computes

an exact solution to an approximate differential equation. (The differential equation is

perturbed in such a way that an exact solution of the perturbed problem is possi-

ble.) This philosophy is opposite to the usual strategy of computing an approximate

solution to the original, exact differential equation. (Chap. 21.)

LIMIT POINT: A point where a solution u(±) of a nonlinear equation curves back so that

there are two solutions for ± on one side of ± = ± limit and no solutions on the other

side of the limit point. As the limit point is approached, du/d± ’ ∞. Special methods

[“pseudoarclength continuation” or “globally convergent homotopy”] are needed to

“turn the corner” and march from the lower branch through the limit point onto the

upper branch or vice versa. Synonyms are “FOLD POINT”, “TURNING POINT”,

and “SADDLE-NODE BIFURCATION”. (Appendix D.)

MARCHING PROBLEM: Arithmurgical slang for a time-dependent problem. It is not

necessary to compute the solution through the entire space-time plane at once. In-

stead, one can march from one time level to the next, computing over all space at

¬xed t independently of the unknown future. See also JURY PROBLEM.

METHOD OF SELECTED POINTS: Synonym for PSEUDOSPECTRAL & ORTHOGONAL

COLLOCATION. (Now rare.)

MMT: MATRIX MULTIPLICATION TRANSFORM: This is N -point interpolation using

N -point Gaussian quadrature or summation of an N -point spectral series at each of

the N grid points. In either direction, the transform is computed by multiplying

an N -dimensional column vector by an N -dimensional square matrix. (PMMT is the

same except that the transform is split into two multiplications by (N/2)-dimensional

square matrices to exploit parity. (Chap. 10.)

NATURAL BOUNDARY CONDITION: A boundary condition is “natural” if it need not

be explicitly imposed, but rather is implicitly satis¬ed by the choice of basis functions.

Examples include periodicity (implicit in Fourier basis) and analyticity at an endpoint

where the coef¬cients of the differential equation are singular (implicit in Chebyshev

basis).

NON-INTERPOLATING: (i) Adjective used to label that family of spectral methods which

do not employ an auxiliary interpolation grid to compute the series coef¬cients.

Galerkin™s method and the Lanczos-tau method are examples (ii) Label for a semi-

Lagrangian time-marching scheme invented by Ritchie (Chap. 14.)

NUMERICAL BOUNDARY CONDITION: A constraint such as u(’1) = ’0.5 which in-

volves a number. It is always necessary to modify either the basis set or the Galerkin

or pseudospectral matrix to enforce such conditions.

Glossary 583

ORTHOGONAL COLLOCATION: A collocation method in which the grid points are the

roots or extrema of the basis functions. Synonym for PSEUDOSPECTRAL.

PARITY: A symmetry of functions such that either f (x) = f (’x) for all x (“SYMMETRIC

with respect to the origin”) or f (x) = ’f (’x) for all x (“ANTISYMMETRIC with

respect to the origin”. A symmetric function is said to be of “even parity” while an

antisymmetric function is said to be of “odd parity”.

PERIODIC: A function f (x) is “periodic” with period L if and only if

f (x + L) = f (x)

for all x.

PMMT: PARITY MATRIX MULTIPLICATION: Same as the MMT except parity is ex-

ploited by taking sums and differences of the input vector to compute its symmetric

and antisymmetric parts and each is transformed separately by a matrix-vector mul-

tiplication. The two transforms are combined to give the transform of the original

unsymmetric series or set of grid point values. (Chap. 10.)

PRECONDITIONING: A technique for accelerating the convergence of an iteration for

solving Λx ’ f by changing the iteration matrix to H ’1 Λ. The matrix H is the “pre-

conditioning matrix” and is chosen to be an approximation to Λ (in the sense of hav-

ing approximately the same eigenvalues), but is much less expensive to invert than Λ.

(Chap. 15.)

PSEUDOSPECTRAL: an algorithm which uses an interpolation grid to determine the co-

ef¬cients of a spectral series. Synonyms are ORTHOGONAL COLLOCATION &

METHOD OF SELECTED POINTS.

RESIDUAL FUNCTION: When an approximate solution uN is substituted into a differ-

ential, integral, or matrix equation, the result is the RESIDUAL function, usually de-

noted R(x; a0 , a1 , . . . , aN ). The residual function would be identically zero if the

approximate solution were exact. (Chap. 1.)

RULE OF THREE NAMES: Every term in this glossary has at least two synonyms.

SEMI-IMPLICIT (TIME-MARCHING): a time-integration method that treats some terms

implicitly and others explicitly. Such algorithms are very common in hydrodynam-

ics where diffusion is treated implicitly but the nonlinear advection is explicit; this

avoids inverting large systems of nonlinear algebraic equations at each time step.

SEMI-LAGRANGIAN: A family of time-marching algorithms for ¬‚uid mechanics which

use the method of characteristics to integrate the advection terms while employing

conventional strategies for the rest. Excellent shock resolution; now widely employed

in numerical weather forecasting. (Chap. 14.)

SEPARABLE: An adjective applied to a partial differential (PDE) equation which denotes

that the PDE can be split into a sequence of ordinary differential equations including

Sturm-Liouville eigenproblems. The procedure for reducing a PDE to ODEs is the

METHOD of SEPARATION of VARIABLES.

SKEW-SYMMETRIC: A matrix A is SKEW-SYMMETRIC if and only if its tranpose is its

T

negative, that is, A = ’A. All eigenvalues of a skew-symmetric matrix are pure

imaginary or zero. Similarly, an operator is skew-symmetric if its adjoint is its nega-

tive; it, too, has pure imaginary eigenvalues.

Glossary

584

SKYLINE SOLVER: An algorithm for the LU FACTORIZATION of a SPARSE matrix which

omits nonzero operations. It is a generalization of a BANDED matrix solver because

the “skyline” allows for different numbers of nonzero elements in different rows (Ap-

pendix B).

SPARSE MATRIX: A matrix whose elements are mostly zero. The opposite of a DENSE

or FULL MATRIX.

SPECTRAL: (i) A catch-all term for all methods (including pseudospectral techiques) which

expand the unknown as a series of global, in¬nitely differentiable expansion func-

tions. (ii) In a narrower sense, it denotes those algorithms that use only the expansion

functions and their integrals and recurrence relations (as opposed to pseudospectral

methods, which need the values of the functions on a grid of interpolation points).

[De¬nition (ii) is not used in this book.]

SPECTRAL BLOCKING: The (spurious) accumulation of energy at or near the smallest

resolved scales. Common in nonlinear hydrodynamics; also arises when the CFL

limit is violated only for the shortest resolvable scales. The signature of spectral

blocking is that the log |an | rises instead of falls with n near n = N , the truncation

limit. The usual remedy is to add a little dissipation which is highly scale-selective,

damping only wavenumbers or coef¬cients close to the truncation limit. (Chap. 11.)

SPECTRAL ELEMENT METHOD: A technique in which the computational domain is

subdivided into several subintervals or blocks and then separate spectral series are

employed on each interval. It differs from the SUBDOMAIN method only by em-

ploying a variational principle and integration-by-parts to more closely parallel ¬nite

element algorithms.

SPECTRAL RINGING: Spurious, small scale oscillations which appear when a function

with a discontinuity or discontinuous slope is approximated by a truncated spectral

series; synonym for GIBBS™ OSCILLATIONS.

SPONGE LAYER: To absorb waves near the ends of a ¬nite interval y ∈ [’L, L] when

domain truncation is used to simulate an in¬nite spatial interval, a large arti¬cial

viscosity is often added in the neighborhood of y = ±L. The regions of large damping

are called “sponge layers” because they absorb the waves so that the center of the

domain is uncorrupted by spurious waves re¬‚ected from y = ±L.

STATIC CONDENSATION: A direct method for solving the matrix equations which re-

sult from ¬nite element or spectral element discretizations. As a ¬rst step, the degrees

of freedom internal to each element are eliminated in favor of the grid point values

on subdomain walls. This generates a dense matrix of much smaller size than the

original sparse matrix, which is then solved by standard LU factorization.

SUBDOMAIN SPECTRAL METHOD: Instead of solving the problem by using a single

series which is valid over the whole domain, the computational region is split into

several smaller regions or “subdomains”. A separate Chebyshev or Legendre expan-

sion is then de¬ned on each subdomain, and the expansions are matched together at

the subdomain boundaries. There are many variants of this strategy, depending upon

whether a variational principle is or is not used and also upon how the algorithm en-

forces continuity from one subdomain to the next. See also SPECTRAL ELEMENTS.

(Chap. 22.)

Glossary 585

SUBGEOMETRIC CONVERGENCE: There are three equivalent de¬nitions. (i) The se-

ries converges exponentially fast with n, but too slowly for the coef¬cients to be

bounded in magnitude by c exp(’pn) for any positive constants c and p. (ii) The

index of exponential convergence r < 1. [r = 1 is “geometric convergence”.]

(iii)

lim log(|an |)/n = 0

n’∞

Subgeometrically-converging series are the expansions of functions which are singu-

lar but in¬nitely differentiable at some point (or points) on the expansion interval

(often at in¬nity). In mathematical jargon, such weakly singular functions “are in

C ∞ , but not C „¦ .”

SUPERGEOMETRIC CONVERGENCE: If the coef¬cients can be bounded by

|an | ¤ O{s exp[’(n/j) log n]}

for suf¬ciently large n and some constants s and j, then the convergence rate is “su-

pergeometric”. This is possible only when the function being expanded is an “entire”

function, that is, one which has no singularities anywhere in the complex plane ex-

cept at ∞.

SUPERIOR LIMIT: For a sequence {an }, the superior limit or supremum limit is writ-

ten lim sup{an } and denotes the lower bound of the almost upper bounds of the se-

quence. (A number is an almost upper bound for a sequence if only a ¬nite number

of members of the sequence exceed the “almost upper bound” in value.) Strictly

speaking, de¬nitions of convergence rates should be expressed in terms of superior

limits, rather than ordinary limits, to allow for oscillations and zeros in the sequence

as n ’ ∞. A synonym is “supremum limit”.

SYMMETRIC: (i) [Of a matrix]: Aij = Aji . (Appendix B.) The longer but more precise

term “CENTROSYMMETRIC” is sometimes used as a synonym. (ii) [Of a function

f (x)]: f (x) = f (’x) for all x. (Chap. 8.)

TAU-METHOD: A mean weighted residual method for which the weighting functions are

the Chebyshev polynomials. Also called the LANCZOS TAU-METHOD. (Chapt. 21.)

TENSOR PRODUCT BASIS: A multi-dimensional basis whose elements are the products

of one-dimensional basis elements. In two dimensions,

¦mn (x, y) ≡ φm (x) ψn (y)

TENSOR PRODUCT GRID: A multi-dimensional grid whose M N points are formed from

the corresponding one-dimensional grids:

xij ≡ (xi , yj ) i = 1, . . . , M & j = 1, . . . , N

TRUNCATION ERROR: The error made by neglecting all coef¬cients an in the spectral

series such that n > N for some “truncation” N .

WEAKLY NONLOCAL SOLITARY WAVE: A steadily-translating, ¬nite amplitude wave

that decays to a small amplitude oscillation (rather to zero) as one moves away from

the core of the disturbance.

Index

adaptive coordinate transformations, see bifurcation point, 544

coordinate transformations,adaptive boundary conditions, 10

algebraic convergence absorbing, 341

calculation of the index for ODE so- basis recombination, 64, 112“115

lution, 43 behavioral versus numerical, 75, 109“

examples 111, 361

half-wave recti¬er function, 22 boundary-bordering, 111“112

sawtooth function, 21 coordinate transformation of bound-

index of, de¬ned, 25 ary conditions on derivatives, 575“

algebraic manipulation language, see sym- 576

bolic manipulation language and homogenization of boundary condi-

spectral methods tions, 112“114

aliasing polar coordinates, at origin, 383

de¬ned, 204 boundary layer, 57

G

Resolution Rule-of-Thumb, 59

equality on the grid (=), 205

symbolic manipulation example, 465

two-h waves, 206

aliasing instability

cardinal functions

dealiasing, 211“216

general orthogonal polynomials, 104

energy-conserving schemes and, 213“

polynomial, de¬ned, 83

216

pseudospectral Chebyshev ODE-solving,

history, 210

115

skew-symmetric advection and, 213

Whittaker, see sinc function

theory, 216“218

Chebyshev polynomials

Two-Thirds Rule for Dealiasing, 211“

asymptotic coef¬cients, calculation of,