11.2 Aliasing and Equality-on-the-Grid

Although our real topic is spatial aliasing, the most familiar examples of aliasing are in

frequency. In a TV western, watch the six-spoked wheels of the stagecoach as it begins to

202

11.2. ALIASING AND EQUALITY-ON-THE-GRID 203

frame

frame

#0

#0

frame #1

frame #1

ω = (2 π) 30 s-1

ω = (2 π) 6 s-1

Figure 11.1: Frequency aliasing. Both panels show the motion of the hands of two clocks as

recorded by a conventional movie camera, which takes a frame every 1/24 of a second. The

left clock hand is turning at a frequency of 6 revolutions/second, so if the hand is vertical

in frame 0, it will be a quarter-turn clockwise in frame 1. The right clock hand is rotating at

30 revolutions/second ” ¬ve times faster. However, on ¬lm, the two stopwatches appear

identical. The hand of the right watch has turned through one-and-a-quarter revolutions in

the 1/24 second interval between frames, so it, too, is pointing to “three o™clock” in frame

1.

The frequency of the high-speed stopwatch has been “aliased” to the lower frequency, 6

turns/second, because a person who watched the ¬lm, even in slow motion, would see the

clock hand turn through only a quarter of a turn [versus the actual ¬ve quarters of a turn]

between frames.

move. If you look carefully, you may see the spokes turning in the wrong direction for a

few moments, then come to rest, and ¬nally begin to rotate in the opposite sense. The same

phenomenon is seen when the propeller of an airplane is started from rest.

The reason for this highly unphysical behavior is that a movie camera cannot contin-

uously photograph a scene; instead, the shutter snaps 24 times per second. This discrete

sampling creates errors that are mathematically identical to those caused by interpolating

a continuous function on a discrete grid of points. Frequencies whose absolute values are

higher than |ω| = 2 π(12)s’1 cannot be properly represented with such a limited sampling.

Instead, the eye ” and mathematics ” interprets the high frequency as some lower fre-

quency on the range

ω ∈ (2π)[’12, 12] s’1 (11.1)

Fig. 11.1 illustrates the problem. The two ¬gures appear identical on ¬lm ” the clock

hand is pointing to 12 o™clock in frame #0 and to 3 o™clock in frame #1. The frequency in

the left frame is only ω = (2 π)6/s while it is ¬ve times higher in the right panel. The

discrete sampling is unable to distinguish between rotation through 90 degrees per frame

and rotation through a full turn plus 90 degrees. To the eye, the higher frequency appears

as the lower frequency ωA = ω ’ (2 π)24/s.

One can show that all frequencies outside the range given by (11.1) will be “aliased” to

a frequency within this range. The upper limit in (11.1) is a motion which rotates through

180 degrees between frames. It might seem as though only frequencies suf¬ciently high

to rotate through a full turn between frames would be aliased. However, if the clock hand

turns through, say, 190 degrees per frame, it is impossible to distinguish this motion from

CHAPTER 11. ALIASING, SPECTRAL BLOCKING, & BLOW-UP

204

one which rotates through - 170 degrees per frame. Indeed, it is these motions which rotate

through more than a half turn but less than a full turn per frame that produce the bizarre

effect of propellers and wheels (apparently) rotating in the wrong direction.

Our real interest is pseudospectral methods rather than cinematic trivia, but the geo-

metric argument is useful because it indicates that high frequencies are not aliased to arbi-

trary frequencies, or to some mix of frequencies. Instead, the aliasing is always through a

positive or negative multiple of one full turn/frame. This is obvious from inspecting the clock

diagram because the eye will always perceive the clock hand as having rotated through

less than half a turn per frame, either clockwise or counterclockwise, regardless of the true

speed of rotation. If the number of rotations (through 360 degrees) per frame is r, then the

viewer will interpret the frequency as

(r ’ m) turns/frame (11.2)

where m is that integer (positive, negative, or zero) such that

1

|r ’ m| < (11.3)

2

Exactly the same applies to spatial aliasing.

De¬nition 23 (ALIASING) If the interval x ∈ [’π, π] is discretized with uniform grid spacing

h, then the wavenumbers in the trigonometric interpolant lie on the range k ∈ [’K, K] where

K ≡ π/h and is the so-called “aliasing limit” wavenumber. The elements of the Fourier basis are

exp[i k x] with k an integer. Higher wavenumbers k such that |k| > K will appear in the numerics

as if they were the wavenumbers

kA = k ± 2 m K m = integer (11.4)

where

kA ∈ [’K, K] (11.5)

The wavenumbers outside the range [’K, K] are said to be “aliased” to wavenumbers within

this range and kA is the “alias” of k.

Eq. (11.4) is merely a restatement of the error law (4.44) for trigonometric interpolation

(Theorem 19) in Chapter 4. There, we stated without proof that if we used N points in

trigonometric interpolation so that cos([N/2]x) was the most rapidly oscillating function

in the basis set, then the computed sine and cosine coef¬cients, {bn } and {an } were con-

taminated by those neglected coef¬cients of the exact series, {±n } and {βn }, as

∞

[Aliasing Law for Cosines in

(11.6)

an = ±|n+mN |

Trigonometric Interpolation]

m=’∞

(on the endpoint/trapezoidal rule grid) and similarly for the sine coef¬cients. Because

K = N/2, (11.6) and (11.4) are equivalent. We have made good the lack of an analytical

proof of the theorem in Chapter 4 by here giving a geometric proof (through clock-faces).

Aliasing may also be stated directly in terms of sines and cosines. Two trigonometric

identities imply

cos([j + mN ] x) = cos(jx) cos(mN x) ’ sin(jx) sin(mN x) (11.7a)

(11.7b)

sin([j + mN ] x) = sin(jx) cos(mN x) + cos(jx) sin(mN x)

11.3. “2 H-WAVES” AND SPECTRAL BLOCKING 205

for arbitrary j and m. When j and m are integers and x is a point on the grid, xi =

2 π i/N, i = 0, 1, . . . , (N ’ 1),

2πk

= cos(2 πk m) = 1 all integral k, m (11.8a)

cos(mN xk ) = cos m N

N

all integral k, m (11.8b)

sin(mN xk ) = 0

In consequence,

G G

(11.9a)

cos(jx) = cos([j + mN ] x) = cos([’j + mN ] x) j = 0, 1, . . .

G G

sin(jx) = sin([j + mN ] x) = ’ sin([’j + mN ] x) (11.9b)

j = 1, . . .

where the “G” above the equals sign denotes that the equality is true only on the N -pt.

evenly spaced grid. Similar relationships exist for the interior (rectangle rule) grid, too.

This special notion of equality ” linearly independent functions that are point-by-point

equal on the grid ” is the essence of aliasing. Canuto et al. (1988, pg. 40) offer a graphic

illustration of (11.9).

Recall that the error in solving differential equations has two components: a truncation

error ET (N ) and a discretization error ED (N ). The truncation error is that of approximat-

ing an in¬nite series as a sum of only N terms. However, there is a second source of error

ED (N ) because the N spectral coef¬cients that we explicitly compute differ from those of

the exact solution.

Aliasing is the reason for these differences in coef¬cients. “Discretization error” and

“aliasing error” are really synonyms.

Aliasing can cause numerical instability in the time integration of nonlinear equations.

For example, a typical quadratically nonlinear term is

« «

K K

= ipx

i q aq eiqx (11.10)

u ux ap e

p=’K q=’K

2K

bk eikx (11.11)

=

k=’2K

where the bk are given by a sum over products of the ak . The nonlinear interaction has

generated high zonal wavenumbers which will be aliased into wavenumbers on the range

k ∈ [’K, K], creating a wholly unphysical cascade of energy from high wavenumbers to

low.

When there is a numerical instability, the earlier assertion that the truncation and dis-

cretization errors are the same order of magnitude is no longer correct; ED can be arbi-

trarily large compared to ET . (Note that the truncation error, which is just the sum of all

the neglected terms of the exact solution, is by de¬nition independent of all time-stepping

errors.) The statement ED ∼ O(ET ) is true only for stable numerical solutions.

11.3 “2 h-Waves” and Spectral Blocking

The onset of aliasing instability can often be detected merely by visual inspection because

the waves at the limit of the truncation ” k = K ” are preferentially excited.

CHAPTER 11. ALIASING, SPECTRAL BLOCKING, & BLOW-UP

206

64 x 64 x 64 96 x 128 x 216

Figure 11.2: Streamwise vorticity contours at t = 22.5 in a transition-to-turbulence model.

The low resolution results are in the left half of the ¬gure; the high resolution at right. The

plot should be symmetric about the dashed line down the middle, so the differences be-

tween left and right halves are due almost entirely to numerical errors in the low resolution

solution (left). Redrawn from Fig. 6 of Zang, Krist and Hussaini (1989).

De¬nition 24 (TWO-H WAVES) Oscillations on a numerical grid which change sign between

adjacent grid points ” and therefore have a wavelength equal to twice the grid spacing h ” are

called “2h-waves”. They are the shortest waves permitted by the numerical grid.

Assertion: a solution with noticeable 2h-waves has almost certainly been damaged by aliasing

or CFL instability.

Fig. 11.2 is an illustration of 2h-waves in a three-dimensional simulation of transition-

to-turbulence. As the ¬‚ow evolves, it develops ¬ner and ¬ner structures and consequently

requires higher and higher resolution. When solved at ¬xed resolution, 2h-waves appear

as seen in the left half of the ¬gure. These are suppressed, without any of the special tricks

described below, merely by using higher resolution (right half of the ¬gure), which is why

these special tricks are controversial.

The 2h-waves are a precursor to breakdown. Although the 643 model still captures

some features at the indicated time, the corresponding plot at the later time, t = 27.5

(Zang, Krist, and Hussaini, 1989), is much noisier and accuracy continues to deteriorate

with increasing time.

The time-dependent increase in 2h-waves must be matched by a growth in the corre-

sponding Fourier coef¬cients, namely those near the aliasing limit K = π/h. This is shown

schematically in Fig. 11.3; an actual spectrum from the same transition-to-turbulence model

is illustrated at different times in Fig. 11.4. The latter graph shows clearly that spectral

blocking is a “secular” phenomenon, that is, it gets worse with time. A numerical simula-

tion which is smooth in its early stages, with monotonically decreasing Fourier or Cheby-

shev coef¬cients, may be very noisy, with lots of 2h-waves and a pronounced upward curl

in the coef¬cient spectrum, for later times.

This curl-up in the absolute values of the Fourier or Chebyshev spectrum near the high-

est resolvable wavenumber (or near TN (x)) has acquired the following name.

11.3. “2 H-WAVES” AND SPECTRAL BLOCKING 207

spectral

blocking

π /h

0 wavenumber k

Figure 11.3: Schematic of “spectral blocking”. Dashed line: logarithm of the absolute values

of Fourier coef¬cients (“spectrum”) at t = 0. Solid: spectrum at a later time. The dashed

vertical dividing line is the boundary in wavenumber between the decreasing part of the

spectrum and the unphysical region where the amplitude increases with k due to numerical

noise and aliasing. The corrupted coef¬cients are marked with disks.

De¬nition 25 (SPECTRAL BLOCKING) If the spectral coef¬cients, when graphed on the usual

logarithm-of-the-absolue value graph, rise with increasing wavenumber or degree near the highest

wavenumber or degree included in the truncation, then this is said to be “spectral blocking”.

The name was coined by ¬‚uid dynamicists. In turbulence, nonlinear interactions cas-

cade energy from smaller to larger k. Very high wavenumbers, with |k| > O(kdiss ) for some

dissipation-scale wavenumber kdiss , will be damped by viscosity, and the coef¬cients will

fall exponentially fast in the dissipation range, k ∈ [kdiss , ∞]. Unfortunately, kdiss for a

high Reynolds ¬‚ow can be so large that even a supercomputer is forced to use a trunca-

tion K << kdiss . Aliasing then blocks the nonlinear cascade and injects energy back into

smaller wavenumbers. This spurious reverse cascade affects all wavenumbers, but is es-

pecially pronounced near the truncation limit k = K because these wavenumbers have

little amplitude except for the erroneous result of aliasing. The numerical truncation has

“blocked” the cascade, and the blocked energy piles up near the truncation limit.

In some ways, the term is misleading because the tendency to accumulate numerical

noise near k = π/h is generic, and not merely a property of turbulence. Nevertheless,

this term has become widely accepted. It is more speci¬c than “high wavenumber noise

accumulation”, which is what spectral blocking really is.

CHAPTER 11. ALIASING, SPECTRAL BLOCKING, & BLOW-UP

208

0

-2

-4 t=18.75

-6