Fast generalized Fourier transforms. (English) Zbl 0677.65143
Computational complexity of the fast generalized Fourier transforms is discussed on the basis of the Wedderburn’s structure theorem. In the sequel, the upper bound of the linear complexity is confidently estimated.
Reviewer: Y.Kobayashi
MSC:
| 65T40 | Numerical methods for trigonometric approximation and interpolation |
| 65R10 | Numerical methods for integral transforms |
| 68Q25 | Analysis of algorithms and problem complexity |
| 42A38 | Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type |
Keywords:
fast Fourier transforms; discrete Fourier transform; discrete Hadamard- Walsh transform; Computational complexity; Wedderburn’s structure theorem; linear complexityReferences:
| [1] | Atkinson, M. D., The complexity of group algebra computations, Theoret. Comput. Sci., 5, 205-209 (1977) · Zbl 0368.20005 |
| [2] | Beth, T., Verfahren der schnellen Fourier-Transformation (1984), Teubner: Teubner Stuttgart · Zbl 0536.65098 |
| [3] | Beth, T., On the computational complexity of the general discrete Fourier transform, Theoret. Comput. Sci., 51, 331-339 (1987) · Zbl 0629.68041 |
| [4] | Bluestein, L. I., A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans., AU-18, 451-455 (1970) |
| [5] | Clausen, M., Fast Fourier transforms for metabelian groups, SIAM J. Comput., 18 (1989) · Zbl 0677.68028 |
| [6] | Cooley, J. W.; Tukey, J. W., An algorithm for the machine calculation of complex Fourier series, Math. Comput., 19, 297-301 (1965) · Zbl 0127.09002 |
| [7] | Curtis, C. W.; Reiner, I., Representation Theory of Finite Groups and Associative Algebras (1962), Wiley: Wiley New York · Zbl 0131.25601 |
| [8] | Huppert, B., Endliche Gruppen I (1967), Springer: Springer Berlin · Zbl 0217.07201 |
| [9] | Hurst, S. L.; Miller, D. M.; Muzio, J. C., Spectral Techniques in Digital Logic (1985), Academic Press: Academic Press New York · Zbl 0628.94017 |
| [10] | James, G. D.; Kerber, A., The Representation Theory of the Symmetric Group (1981), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0491.20010 |
| [11] | Karpovsky, M. G., Fast Fourier transforms on finite non-abelian groups, IEEE Trans. Comput., 26, 1028-1030 (1977) · Zbl 0371.65027 |
| [12] | (Karpovsky, M. G., Spectral Techniques and Fault Detection (1985), Academic Press: Academic Press New York) · Zbl 0625.00027 |
| [13] | Morgenstern, J., Note of a lower bound of the linear complexity of the fast Fourier transform, J. ACM, 20, 305-306 (1973) · Zbl 0258.65120 |
| [14] | Nussbaumer, H. J., Fast Fourier Transform and Convolution Algorithms (1981), Springer: Springer Berlin · Zbl 0599.65098 |
| [15] | Rader, C. M., Discrete Fourier transform when the number of data points is prime, Proc. IEEE, 56, 1107-1108 (1968) |
| [16] | Thrall, R. M., Young’s seminormal representation of the symmetric group, Duke Math. J., 8, 611-624 (1941) · Zbl 0061.04102 |
| [17] | Winograd, S., Proc. Nat. Acad. Sci. USA. Proc. Nat. Acad. Sci. USA, On computing the discrete Fourier transform, 73, 1005-1006 (1976) · Zbl 0323.65050 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
