Remarks on efficient computation of the inverse Fourier transforms on finite non-Abelian groups

Abstract

The Fourier transform is a classical method in mathematical modeling of systems. Assuming finite non-Abelian groups as the underlying mathematical structure might bring advantages in modeling certain systems often met in computer science and information technologies. Frequent computing of the inverse Fourier transform is usually required in dealing with such systems. These computations require for each function value to compute many times traces of certain matrices. These matrices are products of matrix-valued entries of unitary irreducible representations and matrix-valued Fourier coefficients. In the case of large non-Abelian groups the complexity of these computations can be a limiting factor in applications. In this paper, we present a method for speeding-up computing the traces by using decision diagrams to operate on matrix-valued group representations and related Fourier coefficients.