@TechReport{ it:2005-043,
author = {Krister {\AA}hlander},
title = {Sparse Generalized {F}ourier Transforms},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Scientific Computing},
year = {2005},
number = {2005-043},
month = dec,
abstract = {Block-diagonalization of sparse equivariant discretization
matrices is studied. Such matrices typically arise when
partial differential equations that evolve in symmetric
geometries are discretized via the finite element method or
via finite differences.
By considering sparse equivariant matrices as equivariant
graphs, we identify a condition for when
block-diagonalization via a sparse variant of a generalized
Fourier transform (GFT) becomes particularly simple and
fast.
Characterizations for finite element triangulations of a
symmetric domain are given, and formulas for assembling the
block-diagonalized matrix directly are presented. It is
emphasized that the GFT preserves symmetric (Hermitian)
properties of an equivariant matrix.
By simulating the heat equation at the surface of a sphere
discretized by an icosahedral grid, it is demonstrated that
the block-diagonalization pays off. The gain is significant
for a direct method, and modest for an iterative method.
A comparison with a block-diagonalization approach based
upon the continuous formulation is made. It is argued that
the sparse GFT method is an appropriate way to discretize
the resulting continuous subsystems, since the spectrum and
the symmetry are preserved.}
}