# 3Other Fast Algorithms for the FFT

Algorithms for the fast calculation of a discrete Fourier transform (DFT) are based on factorization of the matrix of the transform. We have already seen such factorization in the sections on decimation-in-time and decimation-in-frequency algorithms, in the preceding chapter, which are particular examples of a large group of algorithms.

In order to use these fast algorithms and thus to exploit to the full both the characteristics of the signals to be processed and the various technological possibilities, one must use a suitable mathematical tool – the Kronecker product of matrices. By combining this product with the conventional product, it is possible to factorize the matrix of the DFT in a simple way.

## 3.1 Kronecker Product of Matrices

The Kronecker product is a tensor operation which is a generalization of the multiplication of a matrix by a scalar [1]. Knowing two matrices A and B with m and p rows and n and q columns respectively, the Kronecker product of A by B (written A × B) is a new matrix with mp rows and nq columns, which is obtained by replacing each element bij of the matrix B by the following array bijA:

This product is generally not commutative:

As an example of the product, if the matrix B is

the Kronecker product of the ...

Get Digital Signal Processing, 10th Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.