fftmi
==============================================

Purpose
----------------

Computes a multi-dimensional inverse FFT.

Format
----------------
.. function:: y = fftmi(x, dim)

    :param x: data.
    :type x: Mx1 vector

    :param dim: size of each dimension.
    :type dim: Kx1 vector

    :return y: inverse FFT of *x*.

    :rtype y: Lx1 vector

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 three-dimensional 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 cube
   */
   let x1_1[2, 3] = 1 2 3 4 5 6;
   let x2_1[2, 3] = 6 5 4 3 2 1;
   let x3_1[2, 3] = 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 :func:`vecr` step. Instead we will construct ``x1``, ``x2``, and ``x3`` as vectors to using `let`.

::

    /*
    ** Assign matrices to place in
    ** second 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 :func:`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 multi-dimensional data are laid out in a recursive or hierarchical
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 4-dimensional 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:

.. math::

      X\_hyper = X\_cube1|X\_cube2\\
      X\_cube1 = X\_mat1|X\_mat2\\
      X\_mat1 = X\_row1|X\_row2\\

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 row-major order. This is easy to achieve with :func:`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 :func:`vecr` step
if necessary to get started.

Source
------

fftm.src

.. seealso:: Functions :func:`fft`, :func:`ffti`, :func:`fftn`