Return to Answer

Link to @skbmoore's reference; name of paper

Source Link

edited May 21, 2021 at 19:02

12.9k
4
45
69

Considering a "flop" as a real arithmetic operation and ignoring precision, and apropos of @skbmoore's referencereference, the paper [Johnson, S. G. and Frigo, M. "A Modified Split-Radix FFT With Fewer Arithmetic Operations." IEEE Trans. Sig. Proc. 55, 111 (2007) (doi)] by the authors of FFTW achieves a flop count of $$\frac{43}{9} N \log_2 N - \frac{124}{27} N - 2 \log_2 N - \frac{2}{9}(-1)^{\log_2 N} \log_2 N + \frac{16}{27}(-1)^{\log_2 N} + 8.$$ Here $N$ is assumed a power of two. (See DSPSE answer along these lines here.) In particular, $N = 1,2,4,8,16,32,64,128$ respectively gives flop counts of $4,4,16,56,168,456,1152,2792$. This paper also points out that "no tight lower bound on the flop count is known" in general.

In [Haynal, S. A. and Haynal, H. B. "Generating and searching families of FFT algorithms." J. Satisfiability, Boolean Modeling Comp. 7, 145 (2011) (doi)] the authors show that certain types of FFT algorithm cannot improve on this bound (or indeed in many cases a weaker one) for small $N$.

Finally, this paperBarseghyan and Sarukhanyan - New approach to FFT algorithms claims improved flop counts for $N$.

Considering a "flop" as a real arithmetic operation and ignoring precision, and apropos of @skbmoore's reference, the paper [Johnson, S. G. and Frigo, M. "A Modified Split-Radix FFT With Fewer Arithmetic Operations." IEEE Trans. Sig. Proc. 55, 111 (2007) (doi)] by the authors of FFTW achieves a flop count of $$\frac{43}{9} N \log_2 N - \frac{124}{27} N - 2 \log_2 N - \frac{2}{9}(-1)^{\log_2 N} \log_2 N + \frac{16}{27}(-1)^{\log_2 N} + 8.$$ Here $N$ is assumed a power of two. (See DSPSE answer along these lines here.) In particular, $N = 1,2,4,8,16,32,64,128$ respectively gives flop counts of $4,4,16,56,168,456,1152,2792$. This paper also points out that "no tight lower bound on the flop count is known" in general.

In [Haynal, S. A. and Haynal, H. B. "Generating and searching families of FFT algorithms." J. Satisfiability, Boolean Modeling Comp. 7, 145 (2011) (doi)] the authors show that certain types of FFT algorithm cannot improve on this bound (or indeed in many cases a weaker one) for small $N$.

Finally, this paper claims improved flop counts for $N$.

Considering a "flop" as a real arithmetic operation and ignoring precision, and apropos of @skbmoore's reference, the paper [Johnson, S. G. and Frigo, M. "A Modified Split-Radix FFT With Fewer Arithmetic Operations." IEEE Trans. Sig. Proc. 55, 111 (2007) (doi)] by the authors of FFTW achieves a flop count of $$\frac{43}{9} N \log_2 N - \frac{124}{27} N - 2 \log_2 N - \frac{2}{9}(-1)^{\log_2 N} \log_2 N + \frac{16}{27}(-1)^{\log_2 N} + 8.$$ Here $N$ is assumed a power of two. (See DSPSE answer along these lines here.) In particular, $N = 1,2,4,8,16,32,64,128$ respectively gives flop counts of $4,4,16,56,168,456,1152,2792$. This paper also points out that "no tight lower bound on the flop count is known" in general.

In [Haynal, S. A. and Haynal, H. B. "Generating and searching families of FFT algorithms." J. Satisfiability, Boolean Modeling Comp. 7, 145 (2011) (doi)] the authors show that certain types of FFT algorithm cannot improve on this bound (or indeed in many cases a weaker one) for small $N$.

Finally, Barseghyan and Sarukhanyan - New approach to FFT algorithms claims improved flop counts for $N$.

Source Link

created May 21, 2021 at 18:54

15.4k
7
75
130

Considering a "flop" as a real arithmetic operation and ignoring precision, and apropos of @skbmoore's reference, the paper [Johnson, S. G. and Frigo, M. "A Modified Split-Radix FFT With Fewer Arithmetic Operations." IEEE Trans. Sig. Proc. 55, 111 (2007) (doi)] by the authors of FFTW achieves a flop count of $$\frac{43}{9} N \log_2 N - \frac{124}{27} N - 2 \log_2 N - \frac{2}{9}(-1)^{\log_2 N} \log_2 N + \frac{16}{27}(-1)^{\log_2 N} + 8.$$ Here $N$ is assumed a power of two. (See DSPSE answer along these lines here.) In particular, $N = 1,2,4,8,16,32,64,128$ respectively gives flop counts of $4,4,16,56,168,456,1152,2792$. This paper also points out that "no tight lower bound on the flop count is known" in general.

In [Haynal, S. A. and Haynal, H. B. "Generating and searching families of FFT algorithms." J. Satisfiability, Boolean Modeling Comp. 7, 145 (2011) (doi)] the authors show that certain types of FFT algorithm cannot improve on this bound (or indeed in many cases a weaker one) for small $N$.

Finally, this paper claims improved flop counts for $N$.