Mathematics of Multidimensional Fourier Transform Algorithms

تبدیل فوریه مجموعه داده‌های چند بعدی بزرگ در بسیاری از زمینه‌ها - از لرزه‌شناسی تا تصویربرداری پزشکی - ایجاد می‌شود. افزایش سریع قدرت تراشه های کامپیوتری، افزایش در دسترس بودن پردازشگرهای برداری و آرایه، و افزایش اندازه مجموعه داده های مورد تجزیه و تحلیل، تجزیه و تحلیل داده ها در بیش از یک بعد را در یک زمان ممکن و ضروری می کند. با این حال، افزایش آزادی ارائه شده توسط پردازش چند بعدی، نیازهای شدیدی را بر جنبه‌های ارتباطی محاسبات ایجاد می‌کند و نوشتن کدی را که تمام احتمالات الگوریتمی را در نظر می‌گیرد و با معماری هدف مطابقت می‌دهد، دشوار می‌سازد. این کتاب الگوریتم‌هایی را برای تبدیل فوریه چند بعدی ایجاد می‌کند که کد بسیار کارآمدی را در انواع کامپیوترهای برداری و موازی ارائه می‌دهد. این کتاب با تأکید بر مبنای یکپارچه برای بسیاری از رویکردهای تبدیل فوریه یک‌بعدی و چند بعدی، نه تنها شباهت‌های اساسی را روشن می‌کند، بلکه نحوه بهره‌برداری از تفاوت‌ها در بهینه‌سازی پیاده‌سازی‌ها را نیز نشان می‌دهد. این کتاب نه تنها برای ریاضیدانان کاربردی و دانشمندان کامپیوتر، بلکه برای زلزله‌شناسان، فیزیکدانان پرانرژی، کریستالوگراف‌ها و مهندسان برق که روی پردازش سیگنال و تصویر کار می‌کنند نیز جالب خواهد بود. موضوعات تحت پوشش عبارتند از: محصولات تانسور و تبدیل فوریه سریع. گروه های آبلی محدود و تبدیل فوریه آنها. الگوریتم های کولی-توکی و گود-توماس؛ خطوط و هواپیماها؛ الگوریتم های تبدیل کاهش یافته؛ الگوریتم های میدانی؛ پیاده سازی در Risc و موازی

Fourier transforms of large multidimensional data sets arise in many fields --ranging from seismology to medical imaging. The rapidly increasing power of computer chips, the increased availability of vector and array processors, and the increasing size of the data sets to be analyzed make it both possible and necessary to analyze the data more than one dimension at a time. The increased freedom provided by multidimensional processing, however, also places intesive demands on the communication aspects of the computation, making it difficult to write code that takes all the algorithmic possiblities into account and matches these to the target architecture. This book develops algorithms for multi-dimensional Fourier transforms that yield highly efficient code on a variety of vector and parallel computers. By emphasizing the unified basis for the many approaches to one-dimensional and multidimensional Fourier transforms, this book not only clarifies the fundamental similarities, but also shows how to exploit the differences in optimizing implementations. This book will be of interest not only to applied mathematicians and computer scientists, but also to seismologists, high-energy physicists, crystallographers, and electrical engineers working on signal and image processing. Topics covered include: tensor products and the fast Fourier transform; finite Abelian groups and their Fourier transforms; Cooley- Tukey and Good-Thomas algorithms; lines and planes; reduced transform algorithms; field algorithms; implementation on Risc and parallel