An algorithm for the machine calculation of complex Fourier series
1965/01/01 by James W. Cooley, J.W. Cooley, John W. Tukey · 190 citations
Decision Sciences · Chemical Engineering · Engineering · #Simulation Techniques and Applications #Rheology and Fluid Dynamics Studies #Advanced Numerical Methods in Computational Mathematics
paper · doi:10.1090/s0025-5718-1965-0178586-1
Abstract
An efficient method for the calculation of the interactions of a 2m factorial experiment was introduced by Yates and is widely known by his name.The generalization to 3m was given by Box et al. [1].Good [2] generalized these methods and gave elegant algorithms for which one class of applications is the calculation of Fourier series.In their full generality, Good's methods are applicable to certain problems in which one must multiply an JV-vector by an JV X N matrix which can be factored into m sparse matrices, where m is proportional to log JV.This results in a procedure requiring a number of operations proportional to JV log JV rather than JV2.These methods are applied here to the calculation of complex Fourier series.They are useful in situations where the number of data points is, or can be chosen to be, a highly composite number.The algorithm is here derived and presented in a rather different form.Attention is given to the choice of JV.It is also shown how special advantage can be obtained in the use of a binary computer with JV = 2m and how the entire calculation can be performed within the array of JV data storage locations used for the given Fourier coefficients.Consider the problem of calculating the complex Fourier series
Cited by
- Toroidal and slab ETG instability dominance in the linear spectrum of JET-ILW pedestals
- Convergence analysis of a periodic-like waveform relaxation method for initial-value problems via the diagonalization technique
- Extreme measurements with Photonic Doppler Velocimetry (PDV)
- Hadamard NMR spectroscopy
- Ordered Action Tokens for Visuomotor Policy Learning
- Flash EQ-Linear: Accelerating Equivariant Linear Layers via Group-wise Discrete Fourier Transform
- Computing All Lattice-Rectangle Counts by Rational Staircase Sums
- Multisine electrochemical impedance spectroscopy for Li-ion battery characterisation
- Functional Approximation Methods for Differentially Private Distribution Estimation
- PhasorFlow: A Python Library for Unit Circle Based Computing
- Reaction-Coordinate-Dependent Non-Markovian Friction Governs Protein-Folding Dynamics
- Structure of the Circular-Dyadic Convolution Error
- All elementary functions from a single binary operator
- Position: A Dynamical Systems Perspective is Needed to Advance Time Series Modeling
- Do Models Hear Like Us? Probing the Representational Alignment of Audio LLMs and Naturalistic EEG
- Continuous-Time Piecewise-Linear Recurrent Neural Networks
- Numerical Cosmology
- An algorithm for computing the Nth roots of unity in bit-reversed order
- SPECTRE: An FFT-Based Efficient Drop-In Replacement to Self-Attention for Long Contexts
- Pretest and Stein-Type Estimations in Quantile Regression Model
- Complexity of the Fourier transform on the Johnson graph
- Building Compact and Robust Deep Neural Networks with Toeplitz Matrices
- Functional Gaussian Process Model for Bayesian Nonparametric Analysis
- Distance-preserving Subgraphs of Interval Graphs
- Interval propagation through the discrete Fourier transform
- The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
- The right way to teach the FFT
- Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency
- 1d-qt-ideal-solver: 1D Idealized Quantum Tunneling Solver with Absorbing Boundaries
- Installation and Use of Pulsar Search Software
- O(N) Hierarchical algorithm for computing the expectations of truncated multi-variate normal distributions in N dimensions
- The fast intersection transform with applications to counting paths
- DeepHartree: A Poisson-Coupled Neural Field for One-Shot Density Functional Theory
- Cylindrical Projections of Occupied Diffusions
- The mysteries of the best approximation and Chebyshev expansion for the function with logarithmic regularities
- Deep Legendre Transform
- Towards Ancient Plant Seed Classification: A Benchmark Dataset and Baseline Model
- Theodosian: A Deep Dive into Memory-Hierarchy-Centric FHE Acceleration
- Subset Sampling over Joins
- A Quantum Bluestein's Algorithm for Arbitrary-Size Quantum Fourier Transform
- FADTI: Fourier and Attention Driven Diffusion for Multivariate Time Series Imputation
- Optimization of gridding algorithms for FFT by vector optimization
- An inverse problem for the one-phase Stefan problem with varying melting temperature
- Quantum Computing: Lecture Notes
- mmCounter: Static People Counting in Dense Indoor Scenarios Using mmWave Radar
- Persistent Homology-Guided Frequency Filtering for Image Compression
- Medical Volume Reconstruction Techniques
- Rapid Skill Capture in a First-Person Shooter
- A Superfast Direct Solver for Type-III Inverse Nonuniform Discrete Fourier Transform
- Optimal Hypercontractivity and Log--Sobolev inequalities on Cyclic Groups ℤm⋅ 2k
- Video2Act: A Dual-System Video Diffusion Policy with Robotic Spatio-Motional Modeling
- A Multiscale Sub-linear Time Fourier Algorithm for Noisy Data
- Model-Based Reconstruction for Quantitative MRI using the Bloch Equations
- Using NFFT 3---A Software Library for Various Nonequispaced Fast Fourier Transforms
- Basis Choices for Frequency Domain Statistical Independence Tests and Algorithms for Algebraic Relation Extraction
- Accelerating Probabilistic Response-Time Analysis: Revised Critical Instant and Optimized Convolution
- Upper and lower Higgs boson mass bounds from a chirally invariant lattice Higgs-Yukawa model
- k-Shape
- DeepRFTv2: Kernel-level Learning for Image Deblurring
- Faster Multiplication for Long Binary Polynomials
- Adversarial Multi-Task Learning for Liver Tumor Segmentation, Dynamic Enhancement Regression, and Classification
- The Need for Speed of AI Applications: Performance Comparison of Native\n vs. Browser-based Algorithm Implementations
- INT-DTT+: Low-Complexity Data-Dependent Transforms for Video Coding
- Accurate and Robust Deep Learning Framework for Solving Wave-Based Inverse Problems in the Super-Resolution Regime
- Quasiparticle Variational Quantum Eigensolver
- Algorithms and optimizations for global non-linear hybrid fluid-kinetic finite element stellarator simulations
- Optimized User Experience for Labeling Systems for Predictive Maintenance Applications (Extended)
- Towards Streaming Prediction of Oscillatory Flows: A Data Assimilation and Machine Learning Approach
- Fast Computation on Semirings Isomorphic to (\×, \max) on\n \ℝ+
- Icentia11K: An Unsupervised Representation Learning Dataset for Arrhythmia Subtype Discovery
- Intel HEXL: Accelerating Homomorphic Encryption with Intel AVX512-IFMA52
- Computing Fourier Transforms and Convolutions on the 2-Sphere
- A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable\n Implementations with Guarantees
- MUSTEM: A Dual-Modality System for Vibrotactile and Visual Translation of Music as an Assistive Technology
- Sumudu Neural Operator for ODEs and PDEs
- On Fast Computation of a Circulant Matrix-Vector Product
- MHSXtraPy -- A Python code for the extrapolation of magnetohydrostatic fields on the Sun using analytical solutions
- Fast Bayesian Updates via Harmonic Representations
- Spatial-Frequency Enhanced Mamba for Multi-Modal Image Fusion
- Prime Factor Cyclotomic Fourier Transforms with Reduced Complexity over Finite Fields
- Haptic Assembly and Prototyping: An Expository Review
- Memory-Efficient Training with In-Place FFT Implementation
- Neural Green's Functions
- From Generality to Specificity: Prior-Driven Optimal Sparse Transformation in Compressed Sensing
- Revealing cosmological fluctuations in 21cm intensity maps with MeerKLASS: from maps to power spectra
- A fragile zero-watermarking method based on dual quaternion matrix decomposition
- FFT and orthogonal discrete transform on weight lattices of semi-simple Lie groups
- Neurodatascience: Past, Present, and Future
- Global Filter Networks for Image Classification
- Jaccard dissimilarity in stochastic community models based on the species‐independence assumption
- Intellectual disabilities and power spectra analysis during sleep: a new perspective on borderline intellectual functioning
- Royalists and royalism during the interregnum
- Seventy Years of Radar and Communications: The road from separation to integration
- Practically efficient methods for performing bit-reversed permutation in C++11 on the x86-64 architecture
- On computing the distribution function for the Poisson binomial distribution
- Quantum convolution and quantum correlation algorithms are physically impossible
- Evidence of quantum-entangled higher states of consciousness
- mSDF-DFT: An ultra-low energy discrete Fourier transform architecture for closed-loop neural sensing
- Real-time nonlinear inversion of magnetic resonance elastography with operator learning
- Every matrix is a product of Toeplitz matrices
- Binarized Johnson-Lindenstrauss embeddings
- DaggerFFT: A Distributed FFT Framework Using Task Scheduling in Julia
- Quantum automated theorem proving
- Fast Bayesian Multilevel Quasi-Monte Carlo
- UHKD: A Unified Framework for Heterogeneous Knowledge Distillation via Frequency-Domain Representations
- Circumglobal Rossby wave patterns during boreal winter highlighted by space–time spectral analysis
- Sparse Head-Related Impulse Response for Efficient Direct Convolution
- FourierCompress: Layer-Aware Spectral Activation Compression for Efficient and Accurate Collaborative LLM Inference
- Steady-State Visually Evoked Potentials as Readouts for Abnormal GSK3β Activity in <i>Drosophila</i>
- Fast parallel circuits for the quantum Fourier transform
- Learning Without Augmenting: Unsupervised Time Series Representation Learning via Frame Projections
- Likelihood Methods for the Detection and Characterization of Gamma-ray Pulsars with the Fermi Large Area Telescope
- Depression Detection using Resting State Three-channel EEG Signal
- Compressed Matrix Multiplication
- CrossAD: Time Series Anomaly Detection with Cross-scale Associations and Cross-window Modeling
- F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption (Extended Version)
- Recovery of Integer Images from Limited DFT Measurements with Lattice Methods
- Randomized algorithms for matrices and data
- Seeing Beyond Sound: Visualization and Abstraction in Audio Data Representation
- Improved QFT algorithm for power-of-two FFT
- Practical Verified Computation with Streaming Interactive Proofs
- Polar Separable Transform for Efficient Orthogonal Rotation-Invariant Image Representation
- DC2: A Divide-and-conquer Algorithm for Large-scale Kernel Learning with Application to Clustering
- Wavelet Predictive Representations for Non-Stationary Reinforcement Learning
- Wave-PDE Nets: Trainable Wave-Equation Layers as an Alternative to Attention
- Rasnik 3-point alignment system: algorithm, control framework, and its applications
- Panorama: Fast-Track Nearest Neighbors
- TimeEmb: A Lightweight Static-Dynamic Disentanglement Framework for Time Series Forecasting
- Discrete Wavelet Transform as a Facilitator for Expressive Latent Space Representation in Variational Autoencoders in Satellite Imagery
- Approximation Algorithms for D-optimal Design
- DRIFT-Net: A Spectral--Coupled Neural Operator for PDEs Learning
- Editing Physiological Signals in Videos Using Latent Representations
- S3F-Net: A Multi-Modal Approach to Medical Image Classification via Spatial-Spectral Summarizer Fusion Network
- A FFT-based GMRES for fast solving of Poisson equation in concatenated geometry
- Frequency-Aware Model Parameter Explorer: A new attribution method for improving explainability
- On the Invariance of Cross-Correlation Peak Positions Under Monotonic Signal Transformations, with Application to Fast Time Difference Estimation
- Instantaneous difference frequency locking observed during toroidicity-induced Alfvén eigenmode coupling in the DIII-D tokamak
- A first-principles hetero-integrated Fourier transform system based on memristors
- Active Sensing in Bees Through Antennal Movements Is Independent of Odor Molecule
- Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
- The Hidden Subgroup Problem - Review and Open Problems
- Universal Lattice Basis
- A Two Pronged Progress in Structured Dense Matrix Multiplication
- Degradation-Aware All-in-One Image Restoration via Latent Prior Encoding
- MirrorSAM2: Segment Mirror in Videos with Depth Perception
- ZKProphet: Understanding Performance of Zero-Knowledge Proofs on GPUs
- Unidirectional and collective emission of integrated quantum emitters
- On the Structural Sensitivity of Deep Convolutional Networks to the Directions of Fourier Basis Functions
- On linear differential equations with infinitely many derivatives
- Fast Partial Fourier Transform
- Discrete and Fast Fourier Transform Made Clear
- Towards An Approach to Identify Divergences in Hardware Designs for HPC Workloads
- ButterflyQuant: Ultra-low-bit LLM Quantization through Learnable Orthogonal Butterfly Transforms
simple-idealized-1d-nlse: Pseudo-Spectral Solver for the 1D Nonlinear Schrödinger Equation- Introduction to Number Theoretic Transform
- Coded Fourier Transform
- Accelerated Interactive Auralization of Highly Reverberant Spaces using Graphics Hardware
- From Fourier to Koopman: Spectral Methods for Long-term Time Series Prediction
- A Robust Sparse Fourier Transform in the Continuous Setting
- Anti-scatter grid prototype manufactured via laser powder bed fusion of pure tungsten
- Alignment of the straw tracking detectors for the Fermilab Muon g-2\n experiment and systematic studies for a muon electric dipole moment\n measurement
- Frame multiplication theory and a vector-valued DFT and ambiguity function
- Parallel Programming for FPGAs
- Fast Multipole Method based filtering of non-uniformly sampled data
- FAQ: Questions Asked Frequently
- Fourier Fingerprints of Ansatzes in Quantum Machine Learning
- Filter then Attend: Improving attention-based Time Series Forecasting with Spectral Filtering
- Sparse Linear Networks with a Fixed Butterfly Structure: Theory and\n Practice
- Error bounds for gradient density estimation computed from a finite sample set using the method of stationary phase
- Pauli Stabilizer Models for Gapped Boundaries of Twisted Quantum Doubles and Applications to Composite Dimensional Codes
- Data Science: an Action Plan for Expanding the Technical Areas of the Field of Statistics
- Numerical Solutions to the Sine-Gordon Equation
- Towards Reliable and Generalizable Differentially Private Machine Learning (Extended Version)
- Juggling Functions Inside a Database
- FNT-based Reed-Solomon Erasure Codes
- Optimal smoothing length scale for actuator line models of wind turbine blades
- Frequency-Driven Inverse Kernel Prediction for Single Image Defocus Deblurring
- Representing Speech Through Autoregressive Prediction of Cochlear Tokens
- Sparse and redundant signal representations for x-ray computed tomography
- An in-place truncated Fourier transform and applications to polynomial\n multiplication
- Power Spectrum, Bispectrum, 2- and 3-Point Correlation Function, and Beyond
- TopoLines: Topological Smoothing for Line Charts
- Time multidimensional Markov Renewal chains -- An algebraic approach
- A spectral approach to numerical simulations of the ADM equations
- Enhancing material behavior discovery using embedding-oriented Physically-Guided Neural Networks with Internal Variables
- Signature of a magnetar central engine with precession motion in the X-ray emission of GRB 220711B
- Towards Measuring and Modeling Geometric Structures in Time Series Forecasting via Image Modality
- Non-periodic Fourier propagation algorithms for partial differential equations
- TARS: MinMax Token-Adaptive Preference Strategy for Hallucination Reduction in MLLMs
- Fast Fourier transform [wikipedia]
Related