@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.}
}