In image processing applications Fast Fourier Transforms (FFTs) and
related transformastions are sometimes applied to two-dimensional
images. A two-dimensional FFT can be broken down into a series simpler
one-dimensional FFTs--the one-dimensional transform is simply applied
to every row of the image, then to every column. All rows can
be transformed in parallel, then all columns can be transformed in
parallel. An implementation is given in Figure 4.3
This implementation assumes the availability of a function for
calculating FFTs on one-dimensional *collapsed* arrays (ie,
a sequential one-dimensional FFT). Because Java doesn't have complex
numbers, we store real and imaginary parts in pairs of arrays whose
names are prefixed `re` and `im`. Alternatively a
an extra dimension of extent 2 could be added to the arrays.
After processing all columns, the data is remapped so that each row is
a collapsed subarray. A section dimension naturally inherits the
sequential property (the asterisk in the type signature) from the
associated dimension of the parent array.