@TechReport{ it:2004-029,
author = {Krister {\AA}hlander and Hans Munthe-Kaas},
title = {On Applications of the Generalized Fourier Transform in
Numerical Linear Algebra},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Scientific Computing},
year = {2004},
number = {2004-029},
month = jul,
abstract = {Matrices equivariant under a group of permutation matrices
are considered. Such matrices typically arise in numerical
applications where the computational domain exhibits
geometrical symmetries. In these cases, group
representation theory provides a powerful tool for block
diagonalizing the matrix via the Generalized Fourier
Transform. This technique yields substantial computational
savings in problems such as solving linear systems,
computing eigenvalues and computing analytic matrix
functions.
The theory for applying the Generalized Fourier Transform
is explained, building upon the familiar special (finite
commutative) case of circulant matrices being diagonalized
with the Discrete Fourier Transform. The classical
convolution theorem and diagonalization results are
generalized to the non-commutative case of block
diagonalizing equivariant matrices.
Our presentation stresses the connection between
multiplication with an equivariant matrices and the
application of a convolution. This approach highlights the
role of the underlying mathematical structures such as the
group algebra, and it also simplifies the application of
\textit{fast} Generalized Fourier Transforms. The theory is
illustrated with a selection of numerical examples.}
}