The Triumphal March of the FFT (And the Ambiguities of Comprehension)
March 13, 2007
Book Review
Philip J. Davis
The Evolution of Applied Harmonic Analysis: Models of the Real World. By Elena Prestini, Birkh�user, Boston, 2003, 368 pages, $59.95. (Paperback, based on the author's Applicazioni dell'analisi armonica, Milan, 1996.)
What does it mean to understand something? A silly question? Not at all. I suspect that the deep thinkers of the world have produced thousands of pages by way of answers. Surely the answers vary with the object to be understood, whether a traffic sign, a poem, a facial expression, the U.S. Constitution, a mathematical theorem, a statement in cosmology.
I used to hear this: One does not understand a piece of mathematics until one is able to program it. Richard Feynman told this anecdote:
"During the conference I was staying with my sister in Syracuse. I brought the paper home and said to her �I can't understand these things that Lee and Yang are saying. It's all so complicated.'
"�No,' she said, �what you mean is not that you can't understand it but that you didn't invent it.' "
There are certainly different levels of understanding, from the superficial to the profound, from the casual grasp of someone who can simply repeat a few buzzwords to the "hands on" understanding of the specialist. Deeper understanding may exact a price. The critic Roberston Davies once wrote: "Having discovered what makes the clock go, it is no longer a matter of interest that the clock can tell time." Sadly or wonderfully, there is never a final understanding, for we are always finding new connections and slants and improved explanatory modes. Understanding is an open-ended process.
These remarks are a prelude to a paradox: The book under review is a unique and splendid telling of the triumphs of the fast Fourier transform. I can recommend it unconditionally, and yet I do not really understand half of what the author has written. I explain why shortly.
My first encounter with what has become known as the FFT was as a new BS in mathematics, employed at NACA, Langley Field, Virginia. I was asked to compute the pressure distribution around a two-dimensional airfoil using the well-established algorithm devised by T. Theodorsen in the 1930s. This involved FFT-ing the airfoil profile using 24 or 36 point stencils that encapsulated the symmetries of the sines and cosines and had been laid out by the famous German mathematician Carl Runge.*
Returning to graduate school afterward, with no thought of applications in mind,
I read up on the theory of trigonometric series as laid out in Antoni Zygmund's Trigonometric Series. Trigonometric series have two personalities, the pure and the applied, with the pure questions often going far beyond what is relevant application-wise. Of course, the two say hello to each other more than one might think.
Still later, teaching trigonometric series in courses in approximation theory or advanced numerical methods, I used to tell my students (rightly or wrongly) that of all the advanced pieces of scientific software, the FFT was by far the one called upon most often. But I rarely backed up my claim with concrete instances, and in laying out this review, I wanted to check the claim. I wrote to Cleve Moler (of MATLAB fame and, as of January 1, president of SIAM) for his take on the matter. Cleve answered as follows:
"I've always said that solving systems of simultaneous linear equations is the �most important function' in scientific computing. I have no actual evidence about importance or frequency of use.
"If cell phones actually use the FFT to determine which digit is being dialed, the FFT would certainly be the world's most frequently used algorithm. But I'm not sure whether cell phones actually use the FFT."
Leaving aside the question of which algorithm has "taken the gold," there is no doubt that the FFT is all over the map. Elena Prestini, a professor of mathematics at the University of Rome, "Tor Vergata," has taken one major mathematical idea, that of Fourier analysis, and chased down and described a half dozen varied areas in which Fourier analysis and the FFT are now in place. Her book is much to be applauded, for standard textbooks on methods of applied mathematics (as well as teachers) hasten breathlessly from idea to idea, from method to method, from equation to equation, giving short shrift to the wide variety of situations in which any particular idea is actually in use, either commercially or as part of research programs.
After several initial chapters in which she lays out the basics of Fourier analysis very much as might be found in a standard text, Prestini goes on to present what could be described as mini-monographs in six areas: Fourier Optics and Synchrotron Light, X-Ray Crystallography, Radon Transform and Computerized Tomography, Nuclear Magnetic Resonance, Radio Astronomy, and Sound, Music and Computers. In each area, Prestini outlines the history, personalities of the most important contributors, technical background, theory, recent "down-to-earth" applications, and---almost as throwaway material---analyses via the FFT.
In my view, even if not in the author's, the FFT is the raison d'�tre of the book, and I would have appreciated more details as to how it is actually applied. I suppose that a "mere" piece of software, as fundamental as it may be, can't hold a candle as an attention getter to, say, the structural features of an enzyme or evidence for the Big Bang.
Of these six mini-monographs, I can claim only one that I come even close to understanding: that on sound, music, and computers. Through speaking, playing musical instruments, listening to Pavarotti sing and synthesizers play, I've acquired a certain "hands on," or rather "ears on," experience. I've bolstered this aural experience by looking at lots of pictures of the oscillations produced by saxophones, voices, and so forth.
As regards the other five areas, on a scale of zero to ten---zero meaning incomprehensibility and ten the understanding of a researcher in the field---I would rate my understanding in each at around two. This is by no means Prestini's fault: She has done her work well, describing with care and in considerable depth what is going on. The low ratings reflect my difficulty in understanding what my neighbor just across the hall is doing in his work. But they also reflect a basic semantic difficulty: Each specialty creates a language of its own to provide an interpretation of its particular world, and these languages are by themselves only pale representations of what is the case. This is true whether the world described is that of horse racing, leveraged buyouts, or crystallography. Few of us, alas, are technologically polyglot.
Not infrequently, we sign on with hard cash to the use of some small or large gizmo or megasystem that has emerged from practice and theory. We understand pragmatically what we are getting for our money. I may not understand the chemodynamics of the gasoline inserted into my car, but I understand that the car won't go forward unless I feed it some gas. Therefore, I'm wont to say: Sufficient unto the day is my understanding thereof. Yet in the case of the FFT, I admit to an unfulfilled hankering to know and to understand better the many uses to which it has been put. I don't like to dismiss the matter, either to myself or to my students, by waving my hand and saying: "Ah yes, the FFT? Vibrations, vibrations, vibrations."
And then, what do you know? The FFT has encountered serious competition, and not just from linear equation solvers. Wavelets and chirplets and edgelets are getting into the act, and the number of possible "lets" is large. Acoustic synthesizers may soon be able to simulate Jascha Heifetz playing his Stradivarius in Carnegie Hall, and concert buffs will be able to experience it without ever needing to understand the mathematics that underlies it all.
Philip J. Davis, professor emeritus of applied mathematics at Brown University, is an independent writer, scholar, and lecturer. He lives in Providence, Rhode Island, and can be reached at [email protected].
*P. Terebisi, Rechenschablonen f�r harmonische analyse und synthese nach C. Runge, 1930.
