fftm¶
Purpose¶
Computes a multidimensional FFT.
Format¶

y =
fftm
(x, dim)¶ Parameters:  x (Mx1 vector) – data.
 dim (Kx1 vector) – size of each dimension.
Returns: y (Lx1 vector) – FFT of x.
Examples¶
Here’s an example, this time working with a 2x3x2x3 hypercube. The variable dim contains the dimensions of x, beginning with the highest dimension. The last element of dim is the number of columns, the next to the last element of dim is the number of rows, and so on. Thus
dim = { 2, 3, 3 };
indicates that the data in x represents is a 2x3x3 threedimensional array, i.e., two 3x3 matrices of data.
Suppose that x1 is the first 3x3 matrix and x2 the second 3x3 matrix, then:
x = vecr(x1)  vecr(x2)
The size of dim tells you how many dimensions x has.
// Set dimensions of array
dim = { 2, 3, 2, 3 };
/*
** Assign matrices to place in
** first 3x2x3 cube
*/
x1_1 = { 1 2 3,
4 5 6 };
x2_1 = { 6 5 4,
3 2 1 };
x3_1 = { 1 2 3,
5 7 11 };
/*
** Form cube one by using vecr
** to vectorize x1_1, x2_1, x3_1
** then vertically concatenating
** the results
*/
xc1 = vecr(x1_1)  vecr(x2_1)  vecr(x3_1);
This results in three 2x3 matrices, x1_1
, x2_1
, and x3_1
and an 18x1 vector xc1
:
x1_1 = 1.0000 2.0000 3.0000 x2_1 = 6.0000 5.0000 4.0000 x3_1 = 1.0000 2.0000 3.0000
4.0000 5.0000 6.0000 3.0000 2.0000 1.0000 5.0000 7.0000 11.0000
xc1 = 1.0000
2.0000
3.0000
4.0000
5.0000
6.0000
6.0000
5.0000
4.0000
3.0000
2.0000
1.0000
1.0000
2.0000
3.0000
5.0000
7.0000
11.0000
To assign the second cube we will leave out the vecr()
step. Instead we will construct x1
, x2
, and x3
as vectors.
/*
** Assign matrices to place in
** second 3x2x3 cube
*/
x1_2 = { 1, 1, 2, 3, 5, 8 };
x2_2 = { 1, 2, 6, 24, 120, 720 };
x3_2 = { 13, 17, 19, 23, 29, 31 };
/*
** Form cube two
** by vertically concatenating
** the x1_2, x2_2, and x3_2
** vectors
*/
xc2 = x1_2  x2_2  x3_2;
This results in three 6x1 vectors x1_2
, x2_2
, and x3_2
and an 18x1 vector xc2
:
We will concatenate xc1
and xc2
and use fftm()
to find the Fourier Fast Transform:
// Hypercube
xh = xc1  xc2;
xhfft = fftm(xh, dim);
dimi = { 2, 4, 2, 4 };
xhffti = fftmi(xhfft, dimi);
The arrays have to be padded in each dimension to the nearest power of two. Thus the output array can be larger than the input array.
In this example, xh
is an 36x1 vector and xhfft
is a 64x1 vector. This is because in the case of the
2x3x2x3 hypercube example, x is padded from 2x3x2x3 out to
2x4x2x4. Hence, the input vector contains 36 elements, while the output
vector would contain 64 elements. You may have noticed that we use a
dim with padded values at the end of the example to check our answer.
Remarks¶
The multidimensional data are laid out in a recursive or heirarchical fashion in the vector x. That is to say, the elements of any given dimension are stored in sequence left to right within the vector, with each element containing a sequence of elements of the next smaller dimension. In abstract terms, a 4dimensional 2x2x2x2 hypercubic x would consist of two cubes in sequence, each cube containing two matrices in sequence, each matrix containing two rows in sequence, and each row containing two columns in sequence. Visually, x would look something like this:
Or, in an extended GAUSS notation, x would be:
Xhyper = x[1,.,.,.]  x[2,.,.,.];
Xcube1 = x[1,1,.,.]  x[1,2,.,.];
Xmat1 = x[1,1,1,.]  x[1,1,2,.];
Xrow1 = x[1,1,1,1]  x[1,1,1,2];
To be explicit, x would be laid out like this:
x[1,1,1,1] x[1,1,1,2] x[1,1,2,1] x[1,1,2,2]
x[1,2,1,1] x[1,2,1,2] x[1,2,2,1] x[1,2,2,2]
x[2,1,1,1] x[2,1,1,2] x[2,1,2,1] x[2,1,2,2]
x[2,2,1,1] x[2,2,1,2] x[2,2,2,1] x[2,2,2,2]
If you look at the last diagram for the layout of x, you’ll notice that each line actually constitutes the elements of an ordinary matrix in normal rowmajor order.
This is easy to achieve with vecr()
. Further, each
pair of lines or matrices constitutes one of the desired cubes,
again with all the elements in the correct order. And finally, the two
cubes combine to form the hypercube. So, the process of construction is
simply a sequence of concatenations of column vectors, with a vecr()
step
if necessary to get started.