Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1990 Copyright 1990 Universität Bonn, Institut für Informatik, Abt. V
8551

20.11.2008

Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
Ulrich Baum, Michael Clausen
[Download PostScript] [Download PDF]

The c-linear complexity Lc(A) of a complex matrix A is the minimal number of additions, subtractions and multiplications by complex constants of absolute value ≤ c, c ≥ 2, needed to evaluate A at a generic input vector. Define LS(A) := limc→∞Lc(A). We show that if A is a Fourier transform on the finite group G, then |LS(A) - LS(A-1)| ≤ |G|. The c-linear complexity of a finite group G is defined by Lc(G) := min {Lc(A) | A a Fourier transform of G}. We prove that L2(G) > 1/4|G| log|G| for any finite group G, and present two infinite classes of non-abelian groups G with L2(G) ≤ 0.6|G| log|G| and L2(G) ≤ 0.8|G| log|G|, respectively. Thus there are non-abelian groups with even faster Fourier transforms than elementary abelian 2-groups (for which L2(G) ≤ |G| log|G|) !

Last Change: 11/20/08 at 14:16:05
 English
Universität Bonn -> Institut für Informatik -> Abteilung V