Modified FFTs for fused multiply-add architectures
| Autor: | Elliot Linzer, Ephraim Feig |
|---|---|
| Rok vydání: | 1993 |
| Předmět: | |
| Zdroj: | Mathematics of Computation. 60:347-361 |
| ISSN: | 1088-6842 0025-5718 |
| DOI: | 10.1090/s0025-5718-1993-1159169-0 |
| Popis: | We introduce fast Fourier transform algorithms (FFTs) designed for fused multiply-add architectures. We show how to compute a complex discrete Fourier transform (DFT) of length n = 2 m n = {2^m} with 8 3 n m − 16 9 n + 2 − 2 9 ( − 1 ) m \frac {8}{3}nm - \frac {{16}}{9}n + 2 - \frac {2}{9}{( - 1)^m} real multiply-adds. For real input, this algorithm uses 4 3 n m − 17 9 n + 3 − 1 9 ( − 1 ) m \frac {4}{3}nm - \frac {{17}}{9}n + 3 - \frac {1}{9}{( - 1)^m} real multiply-adds. We also describe efficient multidimensional FFTs. These algorithms can be used to compute the DFT of an n × n n \times n array of complex data using 14 3 n 2 m − 4 3 n 2 − 4 9 n ( − 1 ) m + 16 9 \frac {{14}}{3}{n^2}m - \frac {4}{3}{n^2} - \frac {4}{9}n{( - 1)^m} + \frac {{16}}{9} real multiply-adds. For each problem studied, the number of multiply-adds that our algorithms use is a record upper bound for the number required. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|