Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms (Computational Mathematics) (英語) ハードカバー – 1999/11/11
Kindle 端末は必要ありません。無料 Kindle アプリのいずれかをダウンロードすると、スマートフォン、タブレットPCで Kindle 本をお読みいただけます。
Are some areas of fast Fourier transforms still unclear to you? Do the notation and vocabulary seem inconsistent? Does your knowledge of their algorithmic aspects feel incomplete? The fast Fourier transform represents one of the most important advancements in scientific and engineering computing. Until now, however, treatments have been either brief, cryptic, intimidating, or not published in the open literature. Inside the FFT Black Box brings the numerous and varied ideas together in a common notational framework, clarifying vague FFT concepts.
Examples and diagrams explain algorithms completely, with consistent notation. This approach connects the algorithms explicitly to the underlying mathematics. Reviews and explanations of FFT ideas taken from engineering, mathematics, and computer science journals teach the computational techniques relevant to FFT. Two appendices familiarize readers with the design and analysis of computer algorithms, as well.
This volume employs a unified and systematic approach to FFT. It closes the gap between brief textbook introductions and intimidating treatments in the FFT literature. Inside the FFT Black Box provides an up-to-date, self-contained guide for learning the FFT and the multitude of ideas and computing techniques it employs.
"this book will serve as a self-teaching guide for learning not only FFT, but also many widely applicable techniques in algorithm design and analysis, efficient numerical computation, and scientific programming." --Mathematical Reviews Promo Copy
Most programmers never need to use Fourier transforms. Most of the ones who do will get by quite nicely on black boxes from Mathematica, Matlab, or Numerical Recipes. Data goes in, answers come out, and "a miracle occurs" somewhere in between. There are those times, however, when you can't use the canned routines. You just have to write your own.
This book isn't for the faint-hearted, but really does give everything a non-specialist needs for creating a competent implementation. There's no cut&paste code here, but this is for people with unique needs. It presents a number of basic variations, with clear illustrations and pseudocode. It even discusses 2D transforms, but most of that discussion centers on how to transpose the 2D matrix between 1D transforms.
The discussion of parallel implementation was the only section I found weak. It's aimed at standard sorts of multiprocessors, with specific kinds of connection networks between processors. First, those networks are rare in commercial multiprocessors or are so deeply embedded that the topology is not accessible to the application writer. Second, those networks and architectures miss a lot of important computing environments completely - including the ones important to me.
I don't wish it on anyone, but it might happen - you might have to implement a FFT for yourself. If it does happen, this book may be your most effective tool. It will probably take the non-specialist (like me) time to get past some of the notation, but the answers here are worth the effort.
The book was not as well written as I would have liked. The formula for the split-radix was screwed up. Using the form of the formula and the suggestion of what it represented I was able to derive the formula. It would have been nice if they had written out each term of each iteration for a 64-term fft. That is what I did to see with my own eyes what was happening. The text is too abstract.
All-in-all it was worth the $100.
- 洋書 > Computers & Technology
- 洋書 > Professional & Technical > Engineering > Electrical & Electronics > Electricity Principles
- 洋書 > Professional & Technical > Professional Science > Mathematics > Applied
- 洋書 > Professional & Technical > Professional Science > Mathematics > Mathematical Analysis
- 洋書 > Science > Mathematics > Applied > Differential Equations
- 洋書 > Science > Mathematics > Mathematical Analysis
- 洋書 > Science > Mathematics > Number Systems
- 洋書 > Science > Mathematics > Pure Mathematics > Calculus