On complexity of fast convolution algorithms

Complexity analysis is highly recommended to be based on suitable sequential and parallel machines using arbitrary resources. Traditional complexity predicates are changed completely with respect to fast hardware multipliers, complex arithmetic processing units and the forthcoming VLSI technology. Both signal flow graph derivative and program based complexity analysis are proposed. It is shown that sequential complexity will decrease whereas parallel complexity will increase. The analysis of the last transform step in a transform convolution system carries out an increase of the time complexity at all. Consequently the reduction of the last transform step is resulting in an improved performance of fast transform filter algorithms, especially when the transform size is of moderate small size. This is applicable to the prime factor DFT computation via fast convolution, the WFTA transforms and arbitrary FFT transformations in general.