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.
This initializes the linear algebra packages so that they load as needed.
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). AppendColumns and BlockMatrix from the MatrixManipulation package are 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
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 textual 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.