K
186
4. Series-Expansion Methods
fjJ (x j). 4 Thc basic idea behind the transform method is to compute product tenns
like ca1/l/8x by transfonning c and o1/l/8x from wave number space to physical
space (which takes O(M log M) operations), then multiplying c and onox at
each grid point (requiring O(M) operations), and finally transforming the product
back to wave-number space (which again uses O(M log M) operations). The total number of operations required to evaluate ca1/1/ox via the transform technique
is therefore 0 (M log M), and when the number of Fourier components is large,
it is far more efficient to perform these 0 (M log M) operations than the 0 (M 2 )
operations necessary for the direct computation of (4.26) in wave-number space.
In order to appreciate the degree to which the transform method can improve efficiency, suppose the spectral method is used in a two-dimensional problem in
which the spatial dependence along each coordinate is represented by 128 Fourier
modes; then an order-of-magnitude estimate of the increase in speed allowed by
the transform method is
o ( 128 x 128 ) = 0(1000) .
log2(128 x 128)
The transform method is implemented as folIows. Suppose that one wishes to
determine the Fourier coefficients of the product of fjJ (x) and X(x) such that
fjJ(x)X(x) = L Pk ei kx ,
k=-K
where fjJ and X are periodic on the interval 0 x
2rr and
K
fjJ(x) = L amimx,
m=-K
K
x(x) = L
n=-K
i nx
(4.27)
As just discussed, it is more efficient to transform fjJ and X to physical space,
compute their product in physical space, and to transform the result back to wavenumber space than to compute Pk from the "convolution sum"
r« = L ambn .
m+ n=k
The values of Pk obtained with the transform technique will be identical to those
computed by the preceding summation fonnula, provided that there is sufficient
spatial resolution to avoid aliasing errorl during the computation of the product
4To be specific, if M is apower of two, a transform can be computed in 2M log2 M operations
using the FFT algorithm .
5Aliasing error occurs when a short-wavelength fluctuation is sampled at discrete intervals and
misinterpreted as a longer-wavelength oscillat ion. As discussed in Section 3.5.1. aliasing error can be
generated in attempting to evaluate the product of two poorly resolved waves on a numerical mesh.
186
4. Series-Expansion Methods
fjJ (x j). 4 Thc basic idea behind the transform method is to compute product tenns
like ca1/l/8x by transfonning c and o1/l/8x from wave number space to physical
space (which takes O(M log M) operations), then multiplying c and onox at
each grid point (requiring O(M) operations), and finally transforming the product
back to wave-number space (which again uses O(M log M) operations). The total number of operations required to evaluate ca1/1/ox via the transform technique
is therefore 0 (M log M), and when the number of Fourier components is large,
it is far more efficient to perform these 0 (M log M) operations than the 0 (M 2 )
operations necessary for the direct computation of (4.26) in wave-number space.
In order to appreciate the degree to which the transform method can improve efficiency, suppose the spectral method is used in a two-dimensional problem in
which the spatial dependence along each coordinate is represented by 128 Fourier
modes; then an order-of-magnitude estimate of the increase in speed allowed by
the transform method is
o ( 128 x 128 ) = 0(1000) .
log2(128 x 128)
The transform method is implemented as folIows. Suppose that one wishes to
determine the Fourier coefficients of the product of fjJ (x) and X(x) such that
fjJ(x)X(x) = L Pk ei kx ,
k=-K
where fjJ and X are periodic on the interval 0 x
2rr and
K
fjJ(x) = L amimx,
m=-K
K
x(x) = L
n=-K
i nx
(4.27)
As just discussed, it is more efficient to transform fjJ and X to physical space,
compute their product in physical space, and to transform the result back to wavenumber space than to compute Pk from the "convolution sum"
r« = L ambn .
m+ n=k
The values of Pk obtained with the transform technique will be identical to those
computed by the preceding summation fonnula, provided that there is sufficient
spatial resolution to avoid aliasing errorl during the computation of the product
4To be specific, if M is apower of two, a transform can be computed in 2M log2 M operations
using the FFT algorithm .
5Aliasing error occurs when a short-wavelength fluctuation is sampled at discrete intervals and
misinterpreted as a longer-wavelength oscillat ion. As discussed in Section 3.5.1. aliasing error can be
generated in attempting to evaluate the product of two poorly resolved waves on a numerical mesh.