Fast Fourier transform algorithms for parallel computers. (2019)

• Record Type: Book
• Further Information: Note: Daisuke Takahashi.
• Authors: Takahashi, Daisuke, 1961-
• Contents: Intro; Preface; Contents; 1 Introduction; References; 2 Fast Fourier Transform; 2.1 Definitions of DFT; 2.2 Basic Idea of FFT; 2.3 Cooley-Tukey FFT Algorithm; 2.4 Bit-Reversal Permutation; 2.5 Stockham FFT Algorithm; 2.6 FFT Algorithm for Real Data; 2.6.1 FFT of Two Real Data Simultaneously; 2.6.2 n-Point Real FFT Using n/2-Point Complex FFT; References; 3 Mixed-Radix FFT Algorithms; 3.1 Two-Dimensional Formulation of DFT; 3.2 Radix-3 FFT Algorithm; 3.3 Radix-4 FFT Algorithm; 3.4 Radix-5 FFT Algorithm; 3.5 Radix-8 FFT Algorithm; References; 4 Split-Radix FFT Algorithms 4.1 Split-Radix FFT Algorithm4.2 Extended Split-Radix FFT Algorithm; References; 5 Multidimensional FFT Algorithms; 5.1 Definition of Two-Dimensional DFT; 5.2 Two-Dimensional FFT Algorithm; 5.3 Definition of Three-Dimensional DFT; 5.4 Three-Dimensional FFT Algorithm; Reference; 6 High-Performance FFT Algorithms; 6.1 Four-Step FFT Algorithm; 6.2 Five-Step FFT Algorithm; 6.3 Six-Step FFT Algorithm; 6.4 Blocked Six-Step FFT Algorithm; 6.5 Nine-Step FFT Algorithm; 6.6 Recursive Six-Step FFT Algorithm; 6.7 Blocked Multidimensional FFT Algorithms; 6.7.1 Blocked Two-Dimensional FFT Algorithm 6.7.2 Blocked Three-Dimensional FFT Algorithm6.8 FFT Algorithms Suitable for Fused Multiply-Add (FMA) Instructions; 6.8.1 Introduction; 6.8.2 FFT Kernel; 6.8.3 Goedecker's Technique; 6.8.4 Radix-16 FFT Algorithm; 6.8.5 Radix-16 FFT Algorithm Suitable for Fused Multiply-Add Instructions; 6.8.6 Evaluation; 6.9 FFT Algorithms for SIMD Instructions; 6.9.1 Introduction; 6.9.2 Vectorization of FFT Kernels Using Intel SSE3 Instructions; 6.9.3 Vectorization of FFT Kernels Using Intel AVX-512 Instructions; References; 7 Parallel FFT Algorithms for Shared-Memory Parallel Computers 7.1 Implementation of Parallel One-Dimensional FFT on Shared-Memory Parallel Computers7.1.1 Introduction; 7.1.2 A Recursive Three-Step FFT Algorithm; 7.1.3 Parallelization of Recursive Three-Step FFT; 7.2 Optimizing Parallel FFTs for Manycore Processors; 7.2.1 Introduction; 7.2.2 Parallelization of Six-Step FFT; 7.2.3 Performance Results; References; 8 Parallel FFT Algorithms for Distributed-Memory Parallel Computers; 8.1 Implementation of Parallel FFTs in Distributed-Memory Parallel Computers; 8.1.1 Parallel One-Dimensional FFT Using Block Distribution 8.1.2 Parallel One-Dimensional FFT Using Cyclic Distribution8.1.3 Parallel Two-Dimensional FFT in Distributed-Memory Parallel Computers; 8.1.4 Parallel Three-Dimensional FFT in Distributed-Memory Parallel Computers; 8.2 Computation-Communication Overlap for Parallel One-Dimensional FFT; 8.2.1 Introduction; 8.2.2 Computation-Communication Overlap; 8.2.3 Automatic Tuning of Parallel One-Dimensional FFT; 8.2.4 Performance Results; 8.3 Parallel Three-Dimensional FFT Using Two-Dimensional Decomposition; 8.3.1 Introduction
• Publisher Details: Singapore : Springer
• Publication Date: 2019
• Extent: 1 online resource (ix, 114 pages), illustrations
• Subjects: 004/.35; Parallel processing (Electronic computers) -- Mathematics; Fourier transformations; Electronic books; Electronic books
• Languages: English
• ISBNs: 9789811399657; 9811399654
• Related ISBNs: 9789811399640
• Notes: Note: Includes bibliographical references and index.; Note: Online resource; title from PDF title page (SpringerLink, viewed October 9, 2019).
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.