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
8547

Some lower and upper complexity bounds for generalized Fourier transforms
Ulrich Baum, Michael Clausen
[Download PostScript] [Download PDF]

The 2-linear complexity L2(G) of a finite group G is the minimal number of additions, subtractions and multiplications (by complex constants of absolute value ≤ 2) needed to evaluate a suitable Fourier transform corresponding to 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 12:49:08
 English
Universität Bonn -> Institut für Informatik -> Abteilung V