The FFT is an efficient algorithm for computing the DFT.  The DFT of an arbitrary discrete signal x(n), of length N, is given by

The DFT can be obtained from the Fourier transform X(w) of x(n) by uniformly sampling X(w) at N  points w = wk, k=0,1,…,N-1.  The DFT of the signal x(n) can also be expressed in matrix form, after expanding the summation operation given in (1) as X=FNx.  Here, the signal x(n) and its transform X(k)have been written in column vector form, with their entries in the natural order, starting their indexation at “0” and ending at “N-1” for both the k and n variables.  The matrix FN is then given by

We take the case of N = 4 to provide an example of the DFT 
operation expressed in matrix form.

Thus, the matrix F4 is given by

The computation of the DFT operation has become a very important task in many scientific and engineering applications. Multidimensional computations are of special importance. However, direct computation of these multidimensional operations results in an exceedingly high number of arithmetic operations and large amount of memory use. Take, for instance, a three-dimensional array of real valued data of size 1000 by 1000 by 1000. This size of data is now typical in certain engineering applications. Direct computation of the DFT for this data size will result in a minimum of  arithmetic multiplication operations, with just about the same number of additions.

This example illustrates the need for developing fast algorithms for the efficient computation of large scale DFT’s. For these types of applications, the arithmetic computational effort of the algorithm is in the order of petaflops (10¹⁵ floating point arithmetic operations) and methodologies are being developed for their analysis, design, modification, and efficient implementation. One of these methodologies is based on what is known as Kronecker products algebra.

Kronecker products algebra is a branch of finite-dimensional multilinear algebra that is used for the mathematical formulation of FFT algorithms.  They have been used for modeling algorithms with certain computational structure, which occurs in application areas such as digital signal processing, image processing, digital control system, and statistics. It has been successfully used as an aid to design and implement high performance algorithms for the Discrete Fourier Transform (DFT). The significance of the Kronecker products algebra lies in its ability to model computational structures occurring in a wide spectrum of computer architectures, as well as, the underlying hardware structures, like the interconnection networks.

Let matrices A, B, C be described as follows:

The Kronecker product  of the matrices A and B is the matrix C defined by:

 There exist some Kronecker product expressions, which can be readily identified with specific operations performed on a given computational structure.  Two of the most important ones are the expressions  and , where A and B are square matrices of arbitrary order.  These expressions may be implemented as parallel and vector processing operations, respectively, on machines possessing the required hardware structure.  For example, let F _S denote the discrete Fourier transform (DFT) matrix of order S, then the expression  can be implemented on a machine with vector processor architecture, with at least S vector registers, whose vector length is at least R.  This expression is called the S-point Fourier factor on vectors of length R.

The following are some Kronecker products properties used in the formulation of Fast Fourier Transform (FFT) algorithms.
      1. If  and  are matrices, then

      2. If A and B are nonsingular matrices, then  is non-singular and .

      3. If A and B are matrices, then .

      4. If P and Q are permutation matrices, then is .

      5. If  and  with  , then .

      6. If  and  with  , then .

      7. If  is a matrix, then .

The FFT matrix, F_N, of order N can  be written as the product