<<

. 44
( 136 .)



>>


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

<<

. 44
( 136 .)



>>