Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Free
Faster access than browser!
 

Fast Fourier transform

Index Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components. [1]

154 relations: Academic Press, Advances in Mathematics, ALGLIB, Algorithm, American Federation of Information Processing Societies, American Scientist, Approximation error, Approximation theory, Asymptotically optimal algorithm, Big O notation, Birkhäuser, Bruun's FFT algorithm, Butterfly diagram, C. Sidney Burrus, Cache (computing), Cache-oblivious algorithm, Cambridge University Press, Carl Friedrich Gauss, Central processing unit, Chinese remainder theorem, Chirp Z-transform, Christos Papadimitriou, Circulant matrix, Complex number, Composite number, Computational complexity theory, Computing (journal), Convolution, Convolution theorem, Cooley–Tukey FFT algorithm, Coordinate vector, Coprime integers, Cornelius Lanczos, CRC Press, Cyclotomic polynomial, DFT matrix, Digital signal processing, Dirichlet series, Discrete cosine transform, Discrete Fourier transform, Discrete Fourier transform (general), Discrete Hartley transform, Discrete sine transform, Distributed memory, Divide and conquer algorithm, Electronics Letters, Even and odd functions, External memory algorithm, Factorization, Fast folding algorithm, ..., Fast Fourier transform, Fast multipole method, Fast Walsh–Hadamard transform, FFTPACK, FFTW, Finite field, Fixed-point arithmetic, Floating-point arithmetic, Floating-point unit, Fourier analysis, Fourier transform on finite groups, Frank Yates, Frequency domain, G. C. Danielson, Generalized distributive law, Generating set of a group, Gilbert Strang, Goertzel algorithm, Graph (discrete mathematics), Group (mathematics), Group representation, Group theory, Hadamard transform, Hartley transform, Hexagonal Fast Fourier Transform, IEEE Transactions on Signal Processing, Information Processing Letters, Institute of Electrical and Electronics Engineers, Integer factorization, International Conference on Acoustics, Speech, and Signal Processing, James Cooley, John F. Kennedy, John Tukey, Joseph Fourier, Journal of the ACM, LIGO, Mass spectrometry, Math Kernel Library, Mathematics of Computation, Matrix (mathematics), Matrix decomposition, McGraw-Hill Education, MIT Press, Multidimensional discrete convolution, Multidimensional transform, Multiplication algorithm, Non-uniform discrete Fourier transform, NTi Audio, Number theory, Numerical analysis, Numerical stability, Odlyzko–Schönhage algorithm, OpenStax CNX, Order of magnitude, Overlap–add method, Overlap–save method, Pairwise summation, Parallel computing, Partial differential equation, Pipeline (computing), Polynomial, Power of two, Prentice Hall, Prime number, Prime-factor FFT algorithm, Proceedings of the IEEE, Proof by exhaustion, Proportionality (mathematics), Quantum Fourier transform, Rader's FFT algorithm, Recurrence relation, Recursion, Richard Garwin, Root mean square, Root of unity, Round-off error, Satisfiability modulo theories, Schönhage–Strassen algorithm, Sequence, Shmuel Winograd, SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, Sparse matrix, Spectral density estimation, Spectral music, Spectrum analyzer, Spherical harmonics, SPIE, Split-radix FFT algorithm, Steven G. Johnson, Thomas J. Watson Research Center, Time series, Toeplitz matrix, Transpose, Trigonometric functions, Trigonometric tables, Twiddle factor, Vector-radix FFT algorithm, Victor Pan, Wavelet, Wilkinson Microwave Anisotropy Probe, X-ray crystallography, 2 Pallas, 3 Juno. Expand index (104 more) »

Academic Press

Academic Press is an academic book publisher.

New!!: Fast Fourier transform and Academic Press · See more »

Advances in Mathematics

Advances in Mathematics is a mathematics journal publishing research on pure mathematics.

New!!: Fast Fourier transform and Advances in Mathematics · See more »

ALGLIB

ALGLIB is a cross-platform open source numerical analysis and data processing library.

New!!: Fast Fourier transform and ALGLIB · See more »

Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

New!!: Fast Fourier transform and Algorithm · See more »

American Federation of Information Processing Societies

The American Federation of Information Processing Societies (AFIPS) was an umbrella organization of professional societies established on May 10, 1961 and dissolved in 1990.

New!!: Fast Fourier transform and American Federation of Information Processing Societies · See more »

American Scientist

American Scientist (informally abbreviated AmSci) is an American bimonthly science and technology magazine published since 1913 by Sigma Xi, The Scientific Research Society.

New!!: Fast Fourier transform and American Scientist · See more »

Approximation error

The approximation error in some data is the discrepancy between an exact value and some approximation to it.

New!!: Fast Fourier transform and Approximation error · See more »

Approximation theory

In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby.

New!!: Fast Fourier transform and Approximation theory · See more »

Asymptotically optimal algorithm

In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm.

New!!: Fast Fourier transform and Asymptotically optimal algorithm · See more »

Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

New!!: Fast Fourier transform and Big O notation · See more »

Birkhäuser

Birkhäuser is a former Swiss publisher founded in 1879 by Emil Birkhäuser.

New!!: Fast Fourier transform and Birkhäuser · See more »

Bruun's FFT algorithm

Bruun's algorithm is a fast Fourier transform (FFT) algorithm based on an unusual recursive polynomial-factorization approach, proposed for powers of two by G. Bruun in 1978 and generalized to arbitrary even composite sizes by H. Murakami in 1996.

New!!: Fast Fourier transform and Bruun's FFT algorithm · See more »

Butterfly diagram

In the context of fast Fourier transform algorithms, a butterfly is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms).

New!!: Fast Fourier transform and Butterfly diagram · See more »

C. Sidney Burrus

Charles Sidney Burrus (born October 9, 1934 in Abilene, Texas) is an American electrical engineer and the Maxfield and Oshman Professor Emeritus of Electrical and Computer Engineering at Rice University in Houston, Texas.

New!!: Fast Fourier transform and C. Sidney Burrus · See more »

Cache (computing)

In computing, a cache, is a hardware or software component that stores data so future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation, or the duplicate of data stored elsewhere.

New!!: Fast Fourier transform and Cache (computing) · See more »

Cache-oblivious algorithm

In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a CPU cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter.

New!!: Fast Fourier transform and Cache-oblivious algorithm · See more »

Cambridge University Press

Cambridge University Press (CUP) is the publishing business of the University of Cambridge.

New!!: Fast Fourier transform and Cambridge University Press · See more »

Carl Friedrich Gauss

Johann Carl Friedrich Gauss (Gauß; Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields, including algebra, analysis, astronomy, differential geometry, electrostatics, geodesy, geophysics, magnetic fields, matrix theory, mechanics, number theory, optics and statistics.

New!!: Fast Fourier transform and Carl Friedrich Gauss · See more »

Central processing unit

A central processing unit (CPU) is the electronic circuitry within a computer that carries out the instructions of a computer program by performing the basic arithmetic, logical, control and input/output (I/O) operations specified by the instructions.

New!!: Fast Fourier transform and Central processing unit · See more »

Chinese remainder theorem

The Chinese remainder theorem is a theorem of number theory, which states that if one knows the remainders of the Euclidean division of an integer by several integers, then one can determine uniquely the remainder of the division of by the product of these integers, under the condition that the divisors are pairwise coprime.

New!!: Fast Fourier transform and Chinese remainder theorem · See more »

Chirp Z-transform

The Chirp Z-transform (CZT) is a generalization of the discrete Fourier transform.

New!!: Fast Fourier transform and Chirp Z-transform · See more »

Christos Papadimitriou

Christos Harilaos Papadimitriou (Greek: Χρήστος Χαρίλαος Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist, and professor of Computer Science at Columbia University.

New!!: Fast Fourier transform and Christos Papadimitriou · See more »

Circulant matrix

In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector.

New!!: Fast Fourier transform and Circulant matrix · See more »

Complex number

A complex number is a number that can be expressed in the form, where and are real numbers, and is a solution of the equation.

New!!: Fast Fourier transform and Complex number · See more »

Composite number

A composite number is a positive integer that can be formed by multiplying together two smaller positive integers.

New!!: Fast Fourier transform and Composite number · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: Fast Fourier transform and Computational complexity theory · See more »

Computing (journal)

Computing, subtitled Archives for Scientific Computing, is a scientific journal published by Springer publishing research in computer science and numerical computation.

New!!: Fast Fourier transform and Computing (journal) · See more »

Convolution

In mathematics (and, in particular, functional analysis) convolution is a mathematical operation on two functions (f and g) to produce a third function, that is typically viewed as a modified version of one of the original functions, giving the integral of the pointwise multiplication of the two functions as a function of the amount that one of the original functions is translated.

New!!: Fast Fourier transform and Convolution · See more »

Convolution theorem

In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution is the pointwise product of Fourier transforms.

New!!: Fast Fourier transform and Convolution theorem · See more »

Cooley–Tukey FFT algorithm

The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm.

New!!: Fast Fourier transform and Cooley–Tukey FFT algorithm · See more »

Coordinate vector

In linear algebra, a coordinate vector is a representation of a vector as an ordered list of numbers that describes the vector in terms of a particular ordered basis.

New!!: Fast Fourier transform and Coordinate vector · See more »

Coprime integers

In number theory, two integers and are said to be relatively prime, mutually prime, or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1.

New!!: Fast Fourier transform and Coprime integers · See more »

Cornelius Lanczos

Cornelius (Cornel) Lanczos (Lánczos Kornél,, born as Kornél Lőwy, until 1906: Löwy (Lőwy) Kornél) was a Jewish Hungarian mathematician and physicist, who was born on February 2, 1893, and died on June 25, 1974.

New!!: Fast Fourier transform and Cornelius Lanczos · See more »

CRC Press

The CRC Press, LLC is a publishing group based in the United States that specializes in producing technical books.

New!!: Fast Fourier transform and CRC Press · See more »

Cyclotomic polynomial

In mathematics, more specifically in algebra, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of x^n-1 and is not a divisor of x^k-1 for any.

New!!: Fast Fourier transform and Cyclotomic polynomial · See more »

DFT matrix

In applied mathematics, a DFT matrix is an expression of a discrete Fourier transform (DFT) as a transformation matrix, which can be applied to a signal through matrix multiplication.

New!!: Fast Fourier transform and DFT matrix · See more »

Digital signal processing

Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations.

New!!: Fast Fourier transform and Digital signal processing · See more »

Dirichlet series

In mathematics, a Dirichlet series is any series of the form where s is complex, and a_n is a complex sequence.

New!!: Fast Fourier transform and Dirichlet series · See more »

Discrete cosine transform

A discrete cosine transform (DCT) expresses a finite sequence of data points in terms of a sum of cosine functions oscillating at different frequencies.

New!!: Fast Fourier transform and Discrete cosine transform · See more »

Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.

New!!: Fast Fourier transform and Discrete Fourier transform · See more »

Discrete Fourier transform (general)

In mathematics, the discrete Fourier transform over an arbitrary ring generalizes the discrete Fourier transform of a function whose values are complex numbers.

New!!: Fast Fourier transform and Discrete Fourier transform (general) · See more »

Discrete Hartley transform

A discrete Hartley transform (DHT) is a Fourier-related transform of discrete, periodic data similar to the discrete Fourier transform (DFT), with analogous applications in signal processing and related fields.

New!!: Fast Fourier transform and Discrete Hartley transform · See more »

Discrete sine transform

In mathematics, the discrete sine transform (DST) is a Fourier-related transform similar to the discrete Fourier transform (DFT), but using a purely real matrix.

New!!: Fast Fourier transform and Discrete sine transform · See more »

Distributed memory

In computer science, distributed memory refers to a multiprocessor computer system in which each processor has its own private memory.

New!!: Fast Fourier transform and Distributed memory · See more »

Divide and conquer algorithm

In computer science, divide and conquer is an algorithm design paradigm based on multi-branched recursion.

New!!: Fast Fourier transform and Divide and conquer algorithm · See more »

Electronics Letters

Electronics Letters is a peer-reviewed scientific journal published biweekly by the Institution of Engineering and Technology.

New!!: Fast Fourier transform and Electronics Letters · See more »

Even and odd functions

In mathematics, even functions and odd functions are functions which satisfy particular symmetry relations, with respect to taking additive inverses.

New!!: Fast Fourier transform and Even and odd functions · See more »

External memory algorithm

In computing, external memory algorithms or out-of-core algorithms are algorithms that are designed to process data that is too large to fit into a computer's main memory at one time.

New!!: Fast Fourier transform and External memory algorithm · See more »

Factorization

In mathematics, factorization (also factorisation in some forms of British English) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind.

New!!: Fast Fourier transform and Factorization · See more »

Fast folding algorithm

In signal processing, the fast folding algorithm (Staelin, 1969) is an efficient algorithm for the detection of approximately-periodic events within time series data.

New!!: Fast Fourier transform and Fast folding algorithm · See more »

Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components.

New!!: Fast Fourier transform and Fast Fourier transform · See more »

Fast multipole method

The fast multipole method (FMM) is a numerical technique that was developed to speed up the calculation of long-ranged forces in the ''n''-body problem.

New!!: Fast Fourier transform and Fast multipole method · See more »

Fast Walsh–Hadamard transform

In computational mathematics, the Hadamard ordered fast Walsh–Hadamard transform (FWHTh) is an efficient algorithm to compute the Walsh–Hadamard transform (WHT).

New!!: Fast Fourier transform and Fast Walsh–Hadamard transform · See more »

FFTPACK

FFTPACK is a package of Fortran subroutines for the fast Fourier transform.

New!!: Fast Fourier transform and FFTPACK · See more »

FFTW

The Fastest Fourier Transform in the West (FFTW) is a software library for computing discrete Fourier transforms (DFTs) developed by Matteo Frigo and Steven G. Johnson at the Massachusetts Institute of Technology.

New!!: Fast Fourier transform and FFTW · See more »

Finite field

In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements.

New!!: Fast Fourier transform and Finite field · See more »

Fixed-point arithmetic

In computing, a fixed-point number representation is a real data type for a number that has a fixed number of digits after (and sometimes also before) the radix point (after the decimal point '.' in English decimal notation).

New!!: Fast Fourier transform and Fixed-point arithmetic · See more »

Floating-point arithmetic

In computing, floating-point arithmetic is arithmetic using formulaic representation of real numbers as an approximation so as to support a trade-off between range and precision.

New!!: Fast Fourier transform and Floating-point arithmetic · See more »

Floating-point unit

A floating-point unit (FPU, colloquially a math coprocessor) is a part of a computer system specially designed to carry out operations on floating point numbers.

New!!: Fast Fourier transform and Floating-point unit · See more »

Fourier analysis

In mathematics, Fourier analysis is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions.

New!!: Fast Fourier transform and Fourier analysis · See more »

Fourier transform on finite groups

In mathematics, the Fourier transform on finite groups is a generalization of the discrete Fourier transform from cyclic to arbitrary finite groups.

New!!: Fast Fourier transform and Fourier transform on finite groups · See more »

Frank Yates

Frank Yates FRS (12 May 1902 – 17 June 1994) was one of the pioneers of 20th century statistics.

New!!: Fast Fourier transform and Frank Yates · See more »

Frequency domain

In electronics, control systems engineering, and statistics, the frequency domain refers to the analysis of mathematical functions or signals with respect to frequency, rather than time.

New!!: Fast Fourier transform and Frequency domain · See more »

G. C. Danielson

Gordon C. (G.C.) Danielson was a Distinguished Professor in Sciences and Humanities in 1964 at Iowa State University at Ames, Iowa.

New!!: Fast Fourier transform and G. C. Danielson · See more »

Generalized distributive law

The generalized distributive law (GDL) is a generalization of the distributive property which gives rise to a general message passing algorithm.

New!!: Fast Fourier transform and Generalized distributive law · See more »

Generating set of a group

In abstract algebra, a generating set of a group is a subset such that every element of the group can be expressed as the combination (under the group operation) of finitely many elements of the subset and their inverses.

New!!: Fast Fourier transform and Generating set of a group · See more »

Gilbert Strang

William Gilbert Strang (born November 27, 1934), usually known as simply Gilbert Strang or Gil Strang, is an American mathematician, with contributions to finite element theory, the calculus of variations, wavelet analysis and linear algebra.

New!!: Fast Fourier transform and Gilbert Strang · See more »

Goertzel algorithm

The Goertzel algorithm is a technique in digital signal processing (DSP) that provides a means for efficient evaluation of individual terms of the discrete Fourier transform (DFT), thus making it useful in certain practical applications, such as recognition of DTMF tones produced by the buttons pushed on a telephone keypad.

New!!: Fast Fourier transform and Goertzel algorithm · See more »

Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

New!!: Fast Fourier transform and Graph (discrete mathematics) · See more »

Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set of elements equipped with an operation that combines any two elements to form a third element and that satisfies four conditions called the group axioms, namely closure, associativity, identity and invertibility.

New!!: Fast Fourier transform and Group (mathematics) · See more »

Group representation

In the mathematical field of representation theory, group representations describe abstract groups in terms of linear transformations of vector spaces; in particular, they can be used to represent group elements as matrices so that the group operation can be represented by matrix multiplication.

New!!: Fast Fourier transform and Group representation · See more »

Group theory

In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.

New!!: Fast Fourier transform and Group theory · See more »

Hadamard transform

The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms.

New!!: Fast Fourier transform and Hadamard transform · See more »

Hartley transform

In mathematics, the Hartley transform (HT) is an integral transform closely related to the Fourier transform (FT), but which transforms real-valued functions to real-valued functions.

New!!: Fast Fourier transform and Hartley transform · See more »

Hexagonal Fast Fourier Transform

The Hexagonal Fast Fourier Transform (HFFT) has been developed to utilize the advantages of hexagonal sampling.

New!!: Fast Fourier transform and Hexagonal Fast Fourier Transform · See more »

IEEE Transactions on Signal Processing

The IEEE Transactions on Signal Processing is a biweekly peer-reviewed scientific journal published by the Institute of Electrical and Electronic Engineers covering research on signal processing.

New!!: Fast Fourier transform and IEEE Transactions on Signal Processing · See more »

Information Processing Letters

Information Processing Letters is a peer reviewed scientific journal in the field of computer science, published by Elsevier.

New!!: Fast Fourier transform and Information Processing Letters · See more »

Institute of Electrical and Electronics Engineers

The Institute of Electrical and Electronics Engineers (IEEE) is a professional association with its corporate office in New York City and its operations center in Piscataway, New Jersey.

New!!: Fast Fourier transform and Institute of Electrical and Electronics Engineers · See more »

Integer factorization

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.

New!!: Fast Fourier transform and Integer factorization · See more »

International Conference on Acoustics, Speech, and Signal Processing

ICASSP, the International Conference on Acoustics, Speech, and Signal Processing, is an annual flagship conference organized of IEEE Signal Processing Society.

New!!: Fast Fourier transform and International Conference on Acoustics, Speech, and Signal Processing · See more »

James Cooley

James William Cooley (born 1926, died June 29, 2016) was an American mathematician.

New!!: Fast Fourier transform and James Cooley · See more »

John F. Kennedy

John Fitzgerald "Jack" Kennedy (May 29, 1917 – November 22, 1963), commonly referred to by his initials JFK, was an American politician who served as the 35th President of the United States from January 1961 until his assassination in November 1963.

New!!: Fast Fourier transform and John F. Kennedy · See more »

John Tukey

John Wilder Tukey (June 16, 1915 – July 26, 2000) was an American mathematician best known for development of the FFT algorithm and box plot.

New!!: Fast Fourier transform and John Tukey · See more »

Joseph Fourier

Jean-Baptiste Joseph Fourier (21 March 1768 – 16 May 1830) was a French mathematician and physicist born in Auxerre and best known for initiating the investigation of Fourier series and their applications to problems of heat transfer and vibrations.

New!!: Fast Fourier transform and Joseph Fourier · See more »

Journal of the ACM

The Journal of the ACM is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects.

New!!: Fast Fourier transform and Journal of the ACM · See more »

LIGO

The Laser Interferometer Gravitational-Wave Observatory (LIGO) is a large-scale physics experiment and observatory to detect cosmic gravitational waves and to develop gravitational-wave observations as an astronomical tool.

New!!: Fast Fourier transform and LIGO · See more »

Mass spectrometry

Mass spectrometry (MS) is an analytical technique that ionizes chemical species and sorts the ions based on their mass-to-charge ratio.

New!!: Fast Fourier transform and Mass spectrometry · See more »

Math Kernel Library

Intel Math Kernel Library (Intel MKL) is a library of optimized math routines for science, engineering, and financial applications.

New!!: Fast Fourier transform and Math Kernel Library · See more »

Mathematics of Computation

Mathematics of Computation is a bimonthly mathematics journal focused on computational mathematics.

New!!: Fast Fourier transform and Mathematics of Computation · See more »

Matrix (mathematics)

In mathematics, a matrix (plural: matrices) is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns.

New!!: Fast Fourier transform and Matrix (mathematics) · See more »

Matrix decomposition

In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices.

New!!: Fast Fourier transform and Matrix decomposition · See more »

McGraw-Hill Education

McGraw-Hill Education (MHE) is a learning science company and one of the "big three" educational publishers that provides customized educational content, software, and services for pre-K through postgraduate education.

New!!: Fast Fourier transform and McGraw-Hill Education · See more »

MIT Press

The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts (United States).

New!!: Fast Fourier transform and MIT Press · See more »

Multidimensional discrete convolution

In signal processing, multidimensional discrete convolution refers to the mathematical operation between two functions f and g on an n-dimensional lattice that produces a third function, also of n-dimensions.

New!!: Fast Fourier transform and Multidimensional discrete convolution · See more »

Multidimensional transform

In mathematical analysis and applications, multidimensional transforms are used to analyze the frequency content of signals in a domain of two or more dimensions.

New!!: Fast Fourier transform and Multidimensional transform · See more »

Multiplication algorithm

A multiplication algorithm is an algorithm (or method) to multiply two numbers.

New!!: Fast Fourier transform and Multiplication algorithm · See more »

Non-uniform discrete Fourier transform

In applied mathematics, the nonuniform discrete Fourier transform (NUDFT or NDFT) of a signal is a type of Fourier transform, related to a discrete Fourier transform or discrete-time Fourier transform, but in which the input signal is not sampled at equally spaced points or frequencies (or both).

New!!: Fast Fourier transform and Non-uniform discrete Fourier transform · See more »

NTi Audio

NTi Audio AG is a manufacturer of test and measurement instruments for acoustics, audio and vibration applications.

New!!: Fast Fourier transform and NTi Audio · See more »

Number theory

Number theory, or in older usage arithmetic, is a branch of pure mathematics devoted primarily to the study of the integers.

New!!: Fast Fourier transform and Number theory · See more »

Numerical analysis

Numerical analysis is the study of algorithms that use numerical approximation (as opposed to general symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics).

New!!: Fast Fourier transform and Numerical analysis · See more »

Numerical stability

In the mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms.

New!!: Fast Fourier transform and Numerical stability · See more »

Odlyzko–Schönhage algorithm

In mathematics, the Odlyzko–Schönhage algorithm is a fast algorithm for evaluating the Riemann zeta function at many points, introduced by.

New!!: Fast Fourier transform and Odlyzko–Schönhage algorithm · See more »

OpenStax CNX

OpenStax CNX, formerly called Connexions, is a global repository of educational content provided by volunteers.

New!!: Fast Fourier transform and OpenStax CNX · See more »

Order of magnitude

An order of magnitude is an approximate measure of the number of digits that a number has in the commonly-used base-ten number system.

New!!: Fast Fourier transform and Order of magnitude · See more »

Overlap–add method

In signal processing, the overlap–add method (OA, OLA) is an efficient way to evaluate the discrete convolution of a very long signal x with a finite impulse response (FIR) filter h: \begin y.

New!!: Fast Fourier transform and Overlap–add method · See more »

Overlap–save method

Overlap–save is the traditional name for an efficient way to evaluate the discrete convolution between a very long signal x and a finite impulse response (FIR) filter h: where h.

New!!: Fast Fourier transform and Overlap–save method · See more »

Pairwise summation

In numerical analysis, pairwise summation, also called cascade summation, is a technique to sum a sequence of finite-precision floating-point numbers that substantially reduces the accumulated round-off error compared to naively accumulating the sum in sequence.

New!!: Fast Fourier transform and Pairwise summation · See more »

Parallel computing

Parallel computing is a type of computation in which many calculations or the execution of processes are carried out concurrently.

New!!: Fast Fourier transform and Parallel computing · See more »

Partial differential equation

In mathematics, a partial differential equation (PDE) is a differential equation that contains unknown multivariable functions and their partial derivatives.

New!!: Fast Fourier transform and Partial differential equation · See more »

Pipeline (computing)

In computing, a pipeline, also known as a data pipeline, is a set of data processing elements connected in series, where the output of one element is the input of the next one.

New!!: Fast Fourier transform and Pipeline (computing) · See more »

Polynomial

In mathematics, a polynomial is an expression consisting of variables (also called indeterminates) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables.

New!!: Fast Fourier transform and Polynomial · See more »

Power of two

In mathematics, a power of two is a number of the form where is an integer, i.e. the result of exponentiation with number two as the base and integer as the exponent.

New!!: Fast Fourier transform and Power of two · See more »

Prentice Hall

Prentice Hall is a major educational publisher owned by Pearson plc.

New!!: Fast Fourier transform and Prentice Hall · See more »

Prime number

A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.

New!!: Fast Fourier transform and Prime number · See more »

Prime-factor FFT algorithm

The prime-factor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re-expresses the discrete Fourier transform (DFT) of a size N.

New!!: Fast Fourier transform and Prime-factor FFT algorithm · See more »

Proceedings of the IEEE

The Proceedings of the IEEE is a monthly peer-reviewed scientific journal published by the Institute of Electrical and Electronics Engineers (IEEE).

New!!: Fast Fourier transform and Proceedings of the IEEE · See more »

Proof by exhaustion

Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction, or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases and each type of case is checked to see if the proposition in question holds.

New!!: Fast Fourier transform and Proof by exhaustion · See more »

Proportionality (mathematics)

In mathematics, two variables are proportional if there is always a constant ratio between them.

New!!: Fast Fourier transform and Proportionality (mathematics) · See more »

Quantum Fourier transform

In quantum computing, the quantum Fourier transform (for short: QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform.

New!!: Fast Fourier transform and Quantum Fourier transform · See more »

Rader's FFT algorithm

Rader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution).

New!!: Fast Fourier transform and Rader's FFT algorithm · See more »

Recurrence relation

In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given: each further term of the sequence or array is defined as a function of the preceding terms.

New!!: Fast Fourier transform and Recurrence relation · See more »

Recursion

Recursion occurs when a thing is defined in terms of itself or of its type.

New!!: Fast Fourier transform and Recursion · See more »

Richard Garwin

Richard Lawrence Garwin (born April 19, 1928) is an American physicist, widely known to be the author of the first hydrogen bomb design.

New!!: Fast Fourier transform and Richard Garwin · See more »

Root mean square

In statistics and its applications, the root mean square (abbreviated RMS or rms) is defined as the square root of the mean square (the arithmetic mean of the squares of a set of numbers).

New!!: Fast Fourier transform and Root mean square · See more »

Root of unity

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that gives 1 when raised to some positive integer power.

New!!: Fast Fourier transform and Root of unity · See more »

Round-off error

A round-off error, also called rounding error, is the difference between the calculated approximation of a number and its exact mathematical value due to rounding.

New!!: Fast Fourier transform and Round-off error · See more »

Satisfiability modulo theories

In computer science and mathematical logic, the satisfiability modulo theories (SMT) problem is a decision problem for logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality.

New!!: Fast Fourier transform and Satisfiability modulo theories · See more »

Schönhage–Strassen algorithm

The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers.

New!!: Fast Fourier transform and Schönhage–Strassen algorithm · See more »

Sequence

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed.

New!!: Fast Fourier transform and Sequence · See more »

Shmuel Winograd

Shmuel Winograd (שמואל וינוגרד; born January 4, 1936) is an American computer scientist, noted for his contributions to computational complexity.

New!!: Fast Fourier transform and Shmuel Winograd · See more »

SIAM Journal on Scientific Computing

The SIAM Journal on Scientific Computing (SISC), formerly SIAM Journal on Scientific & Statistical Computing, is a scientific journal focusing on the research articles on numerical methods and techniques for scientific computation.

New!!: Fast Fourier transform and SIAM Journal on Scientific Computing · See more »

Society for Industrial and Applied Mathematics

The Society for Industrial and Applied Mathematics (SIAM) is an academic association dedicated to the use of mathematics in industry.

New!!: Fast Fourier transform and Society for Industrial and Applied Mathematics · See more »

Sparse matrix

In numerical analysis and computer science, a sparse matrix or sparse array is a matrix in which most of the elements are zero.

New!!: Fast Fourier transform and Sparse matrix · See more »

Spectral density estimation

In statistical signal processing, the goal of spectral density estimation (SDE) is to estimate the spectral density (also known as the power spectral density) of a random signal from a sequence of time samples of the signal.

New!!: Fast Fourier transform and Spectral density estimation · See more »

Spectral music

Spectral music (or spectralism) is a compositional technique developed in the 1970s, using computer analysis of the quality of timbre in acoustic music or artificial timbres derived from synthesis.

New!!: Fast Fourier transform and Spectral music · See more »

Spectrum analyzer

A spectrum analyzer measures the magnitude of an input signal versus frequency within the full frequency range of the instrument.

New!!: Fast Fourier transform and Spectrum analyzer · See more »

Spherical harmonics

In mathematics and physical science, spherical harmonics are special functions defined on the surface of a sphere.

New!!: Fast Fourier transform and Spherical harmonics · See more »

SPIE

SPIE is an international not-for-profit professional society for optics and photonics technology, founded in 1955.

New!!: Fast Fourier transform and SPIE · See more »

Split-radix FFT algorithm

The split-radix FFT is a fast Fourier transform (FFT) algorithm for computing the discrete Fourier transform (DFT), and was first described in an initially little-appreciated paper by R. Yavne (1968) and subsequently rediscovered simultaneously by various authors in 1984.

New!!: Fast Fourier transform and Split-radix FFT algorithm · See more »

Steven G. Johnson

Steven G. Johnson is an American mathematician known for being a co-creator of the FFTW library for software-based fast Fourier transforms and for his work on photonic crystals.

New!!: Fast Fourier transform and Steven G. Johnson · See more »

Thomas J. Watson Research Center

The Thomas J. Watson Research Center is the headquarters for IBM Research.

New!!: Fast Fourier transform and Thomas J. Watson Research Center · See more »

Time series

A time series is a series of data points indexed (or listed or graphed) in time order.

New!!: Fast Fourier transform and Time series · See more »

Toeplitz matrix

In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant.

New!!: Fast Fourier transform and Toeplitz matrix · See more »

Transpose

In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal, that is it switches the row and column indices of the matrix by producing another matrix denoted as AT (also written A′, Atr, tA or At).

New!!: Fast Fourier transform and Transpose · See more »

Trigonometric functions

In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are functions of an angle.

New!!: Fast Fourier transform and Trigonometric functions · See more »

Trigonometric tables

In mathematics, tables of trigonometric functions are useful in a number of areas.

New!!: Fast Fourier transform and Trigonometric tables · See more »

Twiddle factor

A twiddle factor, in fast Fourier transform (FFT) algorithms, is any of the trigonometric constant coefficients that are multiplied by the data in the course of the algorithm.

New!!: Fast Fourier transform and Twiddle factor · See more »

Vector-radix FFT algorithm

The vector-radix FFT algorithm, is a multidimensional fast Fourier transform (FFT) algorithm, which is a generalization of the ordinary Cooley–Tukey FFT algorithm that divides the transform dimensions by arbitrary radices.

New!!: Fast Fourier transform and Vector-radix FFT algorithm · See more »

Victor Pan

Victor Yakovlevich Pan (Пан Виктор Яковлевич) is a Soviet and American mathematician and computer scientist.

New!!: Fast Fourier transform and Victor Pan · See more »

Wavelet

A wavelet is a wave-like oscillation with an amplitude that begins at zero, increases, and then decreases back to zero.

New!!: Fast Fourier transform and Wavelet · See more »

Wilkinson Microwave Anisotropy Probe

The Wilkinson Microwave Anisotropy Probe (WMAP), originally known as the Microwave Anisotropy Probe (MAP), was a spacecraft operating from 2001 to 2010 which measured temperature differences across the sky in the cosmic microwave background (CMB) – the radiant heat remaining from the Big Bang.

New!!: Fast Fourier transform and Wilkinson Microwave Anisotropy Probe · See more »

X-ray crystallography

X-ray crystallography is a technique used for determining the atomic and molecular structure of a crystal, in which the crystalline atoms cause a beam of incident X-rays to diffract into many specific directions.

New!!: Fast Fourier transform and X-ray crystallography · See more »

2 Pallas

Pallas, minor-planet designation 2 Pallas, is the second asteroid to have been discovered (after Ceres), and is one of the largest asteroids in the Solar System.

New!!: Fast Fourier transform and 2 Pallas · See more »

3 Juno

Juno, minor-planet designation 3 Juno in the Minor Planet Center catalogue system, is an asteroid in the asteroid belt.

New!!: Fast Fourier transform and 3 Juno · See more »

Redirects here:

Arithmetic complexity of the discrete Fourier transform, Arithmetic complexity of the discrete fourier transform, FFT, FFT algorithm, FFT complexity, Fast Fourier, Fast Fourier Transform, Fast Fourier Transforms, Fast fourier, Fast fourier transform, Fft, IFFT.

References

[1] https://en.wikipedia.org/wiki/Fast_Fourier_transform

OutgoingIncoming
Hey! We are on Facebook now! »