The fast Fourier transform (FFT) is one of the truly great computational developments of this century. It has changed the face of science and engineering so much so that it is not an exaggeration to say that life as we know it would be very different without the FFT.

Unfortunately, the simplicity and intrinsic beauty of many FFT ideas are buried in research papers that are rampant with vectors of subscripts, multiple summations, and poorly specified recursions. The poor mathematical and algorithmic notation has retarded progress and has led to a literature of duplicated results. I am convinced that life as we know it would be considerably different if, from the 1965 Cooley–Tukey paper onwards, the FFT community had made systematic and heavy use of matrix-vector notation! Indeed, by couching results and algorithms in matrix/vector notation, the FFT literature can be unified and made more understandable to the outsider. The central theme in this book is the idea that different FFT algorithms correspond to different factorizations of the discrete Fourier transform (DFT) matrix. The matrix factorization point of view, so successful in other areas of numerical linear algebra, goes a long way toward unifying and simplifying the FFT literature. It closes the gap between the computer implementation of an FFT and the underlying mathematics, because it forces us to think well above the scalar level.

By approaching the FFT matrix/vector terms, the algorithm can be used as a vehicle for studying key aspects of advanced scientific computing, e.g., vectorization, locality of reference, and parallelization. The FFT deserves to be ranked among the great teaching algorithms in computational science such as Gaussian elimination, the Lanczos process, binary search, etc.

I would like to thank a number of colleagues and students for helping to make this book possible. This manuscript began as a set of class notes for a vector-parallel FFT course taught at Cornell in the spring of 1987. The contributions of all the students, especially Clare Chu, Yi-Zhong Wu, Anne Elster, and Nihal Wijeyesekera, are gratefully acknowledged. Clare Chu went on to write a beautiful thesis in the area that has been of immense help to me during the writing of Sections 1.4, 3.5, 4.3, and 4.4.

Sid Burrus’s March 1990 visit to Cornell rejuvenated my interest in the manuscript, which at that time had been dormant for a number of years. I arranged to give a second edition of the FFT course during the fall of that year. Among the attendees who put up with my revisions and expansions of the earlier manuscript, Richard Huff, Wei Li, Marc Parmet, and Stephan Parrett deserve special mention for their contributions to the finished volume. I am also indebted to Dave Bond, Bill Campbell, Greg Henry, Ricardo Pomeranz, Dave Potyondy, and Dean Robinson.

I also wish to thank Chris Paige and Clement Pellerin of McGill University and Lennart Johnsson of Thinking Machines for reading portions of the text and making many corrections and valuable suggestions.

In addition, I would like to acknowledge the financial suppport of the Army Research Office through the Mathematical Sciences Institute (MSI) at Cornell. With the help of the MSI, I was able to organize a workshop on the FFT during the spring of 1987. More recently, I was supported during the summer of 1990 by grants to the Cornell Computational Optimization Project from the Office of Naval Research and the National Science Foundation. During this time, the manuscript was considerably refined.

Finally, I am indebted to Cindy Robinson–Hubbell at the Advanced Computing Research Institute at Cornell for overseeing the production of the camera-ready copy and to Crystal Norris at SIAM for a superb job of copy-editing and managing the whole project.