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
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 comple ...
(DFT) of a size ''N'' = ''N''
1''N''
2 as a two-dimensional ''N''
1×''N''
2 DFT, but ''only'' for the case where ''N''
1 and ''N''
2 are
relatively prime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
. These smaller transforms of size ''N''
1 and ''N''
2 can then be evaluated by applying PFA
recursively
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
or by using some other FFT algorithm.
PFA should not be confused with the ''mixed-radix'' generalization of the popular
Cooley–Tukey algorithm, which also subdivides a DFT of size ''N'' = ''N''
1''N''
2 into smaller transforms of size ''N''
1 and ''N''
2. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called
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. This term was apparently coined by Gentleman & Sande in 1966, and has ...
s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for
power-of-two sizes) and that it requires more complicated re-indexing of the data based on the
additive group
An additive group is a group of which the group operation is to be thought of as ''addition'' in some sense. It is usually abelian, and typically written using the symbol + for its binary operation.
This terminology is widely used with structures ...
isomorphisms
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.
PFA is also closely related to the nested
Winograd FFT algorithm Winograd is a Slavic and Jewish surname:
* Arthur Winograd (1920–2010), original cello player for the '' Juilliard String Quartet''
* David Ostrosky (born David Ostrosky Winograd) a Mexican actor
* Eliyahu Winograd (1926–2018), chairman of th ...
, where the latter performs the decomposed ''N''
1 by ''N''
2 transform via more sophisticated two-dimensional convolution techniques. Some older papers therefore also call Winograd's algorithm a PFA FFT.
(Although the PFA is distinct from the Cooley–Tukey algorithm,
Good
In most contexts, the concept of good denotes the conduct that should be preferred when posed with a choice between possible actions. Good is generally considered to be the opposite of evil and is of interest in the study of ethics, morality, ph ...
's 1958 work on the PFA was cited as inspiration by Cooley and Tukey in their 1965 paper, and there was initially some confusion about whether the two algorithms were different. In fact, it was the only prior FFT work cited by them, as they were not then aware of the earlier research by Gauss and others.)
Algorithm
Let
a polynomial and
a
principal th root of unity. We define the DFT of
as the
-tuple
.
In other words,
:
for all
.
For simplicity, we denote the transformation as
.
The PFA relies on a coprime factorization of
and turns
into
for some choices of
's where
is the
tensor product
In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
.
Mapping Based on CRT
For a coprime factorization
, we have the
Chinese remainder map from
to
with
as its inverse where
's are the
central orthogonal idempotent elements with
.
Choosing
(therefore,
), we rewrite
as follows:
:
.
Finally, define
and
,
we have
.
Therefore, we have the multi-dimensional DFT,
.
As Algebra Isomorphisms
PFA can be stated in a high-level way in terms of
algebra isomorphisms.
We first recall that for a commutative ring
and a
group isomorphism from
to
,
we have the following algebra isomorphism
: