Linear Algebra Packages
The LinearAlgebra portion of the standard add-on packages provide functions for producing orthonormal vectors, solving tridiagonal matrix equations, computing the LU factorization or Cholesky decomposition of a matrix, and other sorts of matrix manipulation.
Fast transform algorithms can be expressed as sparse matrix factorizations. This example shows why the fast Fourier transform (FFT) is faster than the discrete Fourier transform (DFT). BlockMatrix from the MatrixManipulation package is used to demonstrate how the DFT matrix factors into smaller blocks.
The discrete Fourier transform of the sequence is defined by where , or in matrix notation, . The essential idea of the FFT is to find an efficient factorization of the matrix .
This initializes the linear algebra packages so that they load as needed.
is the DFT matrix transforming the input sequence into the output sequence when the sequence length is 4.
Define the block matrix in terms of and the diagonal matrix . This factorization can be related to .
Mathematica's typeset output gives a clear depiction of the block structure of .
Define to be the identity matrix and let be a permutation matrix such that even and odd columns are grouped together. The operation represented by the permutation matrix is referred to as shuffling or twiddling.
BlockMatrix converts , a matrix of submatrices, into a single matrix. This equates the result of applying the DFT to the permutation matrix with the factorization represented by .
Substituting the definition of verifies that the factorization is equivalent to the DFT matrix applied to the permutation matrix .
Since the inverse of the permutation matrix is its transpose, the DFT matrix may be written as the product of two block matrices and a permutation matrix
where denotes the zero matrix. Thus, the DFT can be performed using two smaller DFTs, which are combined with a few multiplies and shuffling. This decomposition of into , where , can be done times. The FFT takes advantage of this decomposition, leading to the time complexity of the FFT versus the time complexity of the DFT.