LINEAR BIJECTIONS AND THE FAST FOURIER TRANSFORM

Markus Hegland and Wayne W. Wheeler Centre for Mathematics and its Applications School of Mathematical Sciences Australian National University Canberra ACT 0200

Abstract. Fast Fourier transform algorithms rely upon the choice of certain bijective mappings between the indices of the data arrays. The two basic mappings used in the literature lead to Cooley–Tukey algorithms or to prime factor algorithms. But many other bijections also lead to FFT algorithms, and a complete classification of these mappings is provided. One particular choice leads to a new FFT algorithm that generalizes the prime factor algorithm. It has the advantage of reducing the floating point operation count by reducing the number of trigonometric function evaluations. A certain equivalence relation is defined on the set of bijections that lead to FFT algorithms, and its connection with isomorphism classes of group extensions is studied. Under this equivalence relation every equivalence class contains bijections leading to an FFT algorithm of the new type.

1. Introduction

Fast Fourier transform (FFT) algorithms are among the most important applications of scientific computing, and their availability since the 1960’s has revolutionized signal processing and computational science. These algorithms can be based on the algebraic idea of group representations of cyclic groups, as discussed in Section 2. In this framework fast Fourier transform algorithms have been generalized to certain types of nonabelian groups [3, 4, 5].

Another approach to studying FFT algorithms involves the idea of representing the indices of the data array in a manner analogous to the decimal representation of an integer in terms of digits. For example, suppose that the index j varies over the range 0 ≤ j ≤ n − 1, and assume that n = n_{1}n_{2}. If s ∈ ℤ, let ⟨s⟩_{n} denote the unique integer t such that 0 ≤ t ≤ n−1 and s ≡ t (mod n). For any integers a_{1} and a_{2} there is a function ϕ : {0, 1, …, n_{1} − 1} × {0, 1, …, n_{2} − 1} → {0, 1, …, n − 1} given by

ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1} + a_{2}j_{2}⟩_{n}.

If a_{1} and a_{2} are chosen so that ϕ is a bijection, then one can think of j_{1} and j_{2} as the digits of j = ϕ(j_{1}, j_{2}). More generally, if n = n_{1} ⋯ n_{t}, then one can use similar ideas to produce a representation of j in terms of t digits.

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 65T20.

Key words and phrases. Fast Fourier transform, prime factor algorithm, splitting pair.

One question that naturally arises in the two-digit case, then, is how to choose the constants a_{s} so that ϕ will be a bijection. The answer to this question was originally suggested by Burrus [2], and in Section 3 we provide a proof. Among other things, the proof shows that the set B of all bijections breaks up into two natural subsets B_{1} and B_{2}. An FFT algorithm depends upon a choice of two bijections ϕ and ψ, and in Section 4 we show that such an algorithm arises if and only if either (ϕ, ψ) ∈ B_{1} × B_{2} or (ϕ, ψ) ∈ B_{2} × B_{1}. In this situation we refer to (ϕ, ψ) as a splitting pair because these pairs define the setting for what is usually called a splitting in [13].

Actual FFT algorithms operate recursively, and a variety of different algorithms are obtained by choosing different combinations of splitting pairs. Particular choices lead to decimation in time, decimation in frequency, and other possibilities described in [7]. The classical Cooley–Tukey procedure consists of a number of Fourier transform calculations of sizes n_{1} and n_{2}, a data rearrangement step, and one intermediate step consisting of multiplication by certain n^{th} roots of unity called twiddle factors. On the other hand, if n_{1} and n_{2} are relatively prime, then prime factor splitting can be used. The resulting algorithm has the advantage that it is not necessary to multiply by a twiddle factor, so the computations require not only fewer complex multiplications but also fewer sine and cosine evaluations. Because the rounding errors of FFT algorithms are mainly due to errors in the trigonometric functions used, the prime factor algorithm can be both faster and more precise than the Cooley–Tukey algorithm.

In Section 4 we single out a particular type of splitting pair, called a maximal pair, that generalizes prime factor splitting and has some advantages over Cooley– Tukey splitting. In particular, the pair is designed to reduce as far as possible the number of twiddle factors that must be computed in the resulting FFT algorithm. In certain cases either Cooley–Tukey splitting or prime factor splitting will be maximal, but in general a maximal splitting pair will produce an FFT algorithm that is different from both the Cooley–Tukey algorithm and the prime factor algorithm.

One consequence of the characterization of the set of bijections B is that every bijection determines an extension of abelian groups. Equivalence classes of extensions correspond to 2-cocycles; these are certain functions that are closely related to the process of carrying when adding two integers represented in terms of digits. The resulting algebraic relationships are studied in Sections 5 and 6. In particular, because there is a standard equivalence relation on extensions of abelian groups, we get a corresponding relation on bijections. This in turn allows us to define an equivalence relation on splitting pairs, and in Section 7 we show that every equivalence class contains a maximal splitting pair. Thus we are able to provide a connection between fast Fourier transforms and the algebraic theory of group extensions.

2. Group Representations and the Fast Fourier Transform

In this section we describe the relationship between fast Fourier transform algorithms and group representations. This connection forms the basis for work that has generalized FFT algorithms from abelian groups to metabelian and symmetric groups in recent years [4, 5].

Let G be a group of order n, and let D_{1}, …, D_{t} be a set of representatives for the equivalence classes of irreducible matrix representations of the group algebra ℂG. Set d_{j} = dim D_{j} for 1 ≤ j ≤ t. The representation

D = ⨁_{j=1}^{t} D_{j}

of ℂG is called the Wedderburn transform. It is an algebra isomorphism between ℂG and the algebra ⊕_{j=1}^{t}ℂ^{d_{j}×d_{j}} of block diagonal matrices. From a computational point of view the Wedderburn transform is a linear transformation between two complex n-dimensional vector spaces and is essentially a complex matrix-vector product. Thus the number of floating point operations (additions and multiplications of floating point reals) is of the order O(n^{2}) for a straightforward implementation. Fast generalized Fourier transform algorithms improve upon this bound; in the case of abelian groups it is well known that FFT algorithms can be done with O(n log n) floating point operations [13].

Fast generalized Fourier transform algorithms are based on the process of partitioning the group G into cosets. Suppose that the order of G factors as n = n_{1}n_{2} with n_{1}, n_{2} > 1. Let H be a subgroup of order n_{2}, and let g_{1}, …, g_{n_{1}} be a complete set of representatives for the left cosets of H in G. Then G can be written as a disjoint union

G = ⋃_{j=1}^{n_{1}} g_{j}H.

If x ∈ ℂG, then there are constants x_{j,h} ∈ ℂ such that

x = ∑_{j=1}^{n_{1}} ∑_{h∈H} x_{j,h}g_{j}h = ∑_{j=1}^{n_{1}} g_{j} ( ∑_{h∈H} x_{j,h}h) .

Because D is an algebra homomorphism, it follows that

D(x) = ∑_{j=1}^{n_{1}} D(g_{j}) ∑_{h∈H} x_{j,h}D(h).

The Wedderburn transform can therefore be calculated in two steps: first compute the sums

z_{j} = ∑_{h∈H} x_{j,h}D(h)

and then the sum

D(x) = ∑_{j=1}^{n_{1}} D(g_{j})z_{j}.

Note that the restriction of D to ℂH is a representation, but it is not a Wedderburn transform because it contains representations of ℂH that are equivalent. Consequently, there is a certain redundancy involved in computing z_{j}, and it is the process of exploiting this redundancy that makes the FFT algorithms efficient. For different types of groups, however, the actual implementations can be quite different [1, 3, 4, 5]; it appears that the choice of the subgroup H and the coset representatives g_{1}, …, g_{n_{1}} is critical.

When G is abelian, the Wedderburn transform is generally referred to as the discrete Fourier transform. It is well known that in this case all the irreducible representations of G are one-dimensional. Furthermore, they form an abelian group G^{∗}, called the dual or character group, and G^{∗} is isomorphic to G. The dual group (G/H)^{∗} can be identified with the subgroup H^{⊥} of G^{∗} consisting of those representations D_{j} with D_{j}(h) = 1 for all h ∈ H. Let χ_{1}, …, χ_{n_{2}} be a complete set of representatives for the cosets of H^{⊥} in G^{∗}. Then the representation of H given by

h ↦ ⨁_{k=1}^{n_{2}} χ_{k}(h)

is a Wedderburn transform for H, the representation of G/H given by

g_{j}H ↦ ⨁_{λ∈H^{⊥}} λ(g_{j})

is a Wedderburn transform for G/H, and the representation of G given by

g_{j}h ↦ ⨁_{\begin{matrix}λ∈H^{⊥} \\ 1≤k≤n_{2} \end{matrix}} λ(g_{j})χ_{k}(g_{j})χ_{k}(h)

is a Wedderburn transform for G. If x ∈ ℂG is given by

x = ∑_{j=1}^{n_{1}} g_{j} ( ∑_{h∈H} x_{j,h}h) ,

then the components of the Wedderburn transform of x are the quantities

y_{λ,k} = ∑_{j=1}^{n_{1}} λ(g_{j})χ_{k}(g_{j}) ∑_{h∈H} χ_{k}(h)x_{j,h}

for all λ ∈ H^{⊥} and k = 1, …, n_{2}. Each of these components can be calculated in three steps:

(1)  u_{j,k} = ∑_{h∈H} χ_{k}(h)x_{j,h};
(2)  v_{j,k} = χ_{k}(g_{j})u_{j,k};
(3)  y_{λ,k} = ∑_{j=1}^{n_{1}} λ(g_{j})v_{j,k}.

Because the first and third steps again involve Wedderburn transforms, the procedure can be applied recursively. Note that replacing g_{j} or χ_{k} by another element in the same coset does not affect the computation in the first or third steps; the particular coset representatives are crucial only in the second step, which consists of multiplying by the so-called twiddle factors χ_{k}(g_{j}).

The choice of the subgroup H and the coset representatives g_{1}, …, g_{n_{1}} and χ_{1}, …, χ_{n_{2}} can have a strong effect upon the complexity of the resulting algorithm. For example, in the prime factor algorithm the choices are made so that χ_{k}(g_{j}) = 1 for all j and k. While this does make the second step unnecessary, it is not always achievable.

Now suppose that G is a cyclic group of order n generated by an element g. Then both G/H and G^{∗}/H^{⊥} are also cyclic. If g_{1}H is a generator of G/H and χ_{1}H^{⊥} is a generator of G^{∗}/H^{⊥}, then the coset representatives can be chosen so that g_{j} = g_{1}^{j} and χ_{k} = χ_{1}^{k} for all j and k. Let a_{1} and a_{2} be integers with 0 ≤ a_{1}, a_{2} ≤ n − 1 such that g_{1} = g^{a_{1}} and H is generated by g^{a_{2}}. Then any element of G can be given by specifying a double index (j_{1}, j_{2}) with 0 ≤ j_{1} ≤ n_{1} − 1 and 0 ≤ j_{2} ≤ n_{2} − 1; one index determines a coset representative, and the other index determines an element of H. This double index then corresponds to the element g^{a_{1}j_{1}+a_{2}j_{2}}. If ϕ(j_{1}, j_{2}) denotes the integer with 0 ≤ ϕ(j_{1}, j_{2}) ≤ n − 1 such that ϕ(j_{1}, j_{2}) ≡ a_{1}j_{1} + a_{2}j_{2} (mod n), then it follows that g^{ϕ(j_{1},j_{2})} = g^{a_{1}j_{1}+a_{2}j_{2}}, and the function ϕ : {0, …, n_{1}− 1} × {0, …, n_{2} − 1} → {0, …, n − 1} is a bijection. Similarly, if χ is a generator of G^{∗}, then there is a bijection ψ : {0, …, n_{1} − 1} × {0, …, n_{2} − 1} → {0, …, n − 1} such that the double index (k_{1}, k_{2}) corresponds to the element χ^{ψ(k_{1},k_{2})} ∈ G^{∗}. The functions ϕ and ψ in turn determine the subgroup H and the coset representatives.

Provided that the coset representatives are chosen so that g_{j} = g_{1}^{j} and χ_{k} = χ_{1}^{k}, it is therefore possible to study FFTs for cyclic groups by considering pairs of bijections (ϕ, ψ) instead of the subgroup H and the various coset representatives. In fact, if ω_{n} = e^{−2π\sqrt{−1}/n}, then g_{1} and χ_{1} can be chosen so that χ_{1}(g_{1}) = ω_{n}. Moreover, an element x ∈ ℂG can be considered as an n-tuple (x_{0}, …, x_{n−1}) ∈ ℂ^{n} in which

x = ∑_{j=0}^{n−1} x_{j}g^{j}.

The discrete Fourier transform can then be regarded as a linear transformation mapping the n-tuple (x_{0}, …, x_{n−1}) ∈ ℂ^{n} to another n-tuple (y_{0}, …, y_{n−1}) ∈ ℂ^{n} given by

y_{k} = ∑_{j=0}^{n−1} ω_{n}^{kj}x_{j}

for 0 ≤ k ≤ n − 1. This is the classical approach to the discrete Fourier transform. It is also the point of view we take in the remainder of the paper, which uses pairs of bijections (ϕ, ψ) to carry out a systematic study of the choices involved in FFT algorithms. One result is the development of a new type of algorithm that reduces the number of different twiddle factors, thereby increasing the efficiency and the precision at the same time.

3. Linear Bijections

If n ∈ ℕ, then for the remainder of this paper we will write ℤ_{n} for the abelian group of integers {0, 1, …, n − 1} under addition modulo n; if j ∈ ℤ, then ⟨j⟩_{n} will be used to denote the unique integer t ∈ ℤ_{n} such that j ≡ t (mod n); and if j_{1}, …, j_{s} are integers, then (j_{1}, …, j_{s}) denotes the greatest common divisor of j_{1}, …, j_{s}.

Assume that n = n_{1}n_{2} for some natural numbers n_{1} and n_{2}. We will say that a function ϕ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} is linear if there are numbers a_{1}, a_{2} ∈ ℤ_{n} such that

ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1} + a_{2}j_{2}⟩_{n}.

In general ϕ will not be a group homomorphism. The problem we want to study here, however, is to describe the conditions under which ϕ defines a bijection between the underlying sets. An answer to this problem has been given without proof by Burrus [2]. His answer can easily be restated in the following form.

Theorem 3.1. The function ϕ is a linear bijection if and only if one of the following conditions is satisfied:

(1) (a_{1}, n) = n_{2} and (a_{2}, n_{2}) = 1.

(2) (a_{2}, n) = n_{1} and (a_{1}, n_{1}) = 1.

Most of this section is devoted to giving a proof of Theorem 3.1. We end by stating a conjecture that would give a generalization for bijections ℤ_{n_{1}} ×⋯×ℤ_{n_{t}} → ℤ_{n} when n = n_{1} ⋯ n_{t}.

Lemma 3.2. Suppose that ϕ is a linear bijection. Then there is an integer s ∈ ℤ_{n_{2}} such that n_{1}a_{1} ≡ a_{2}s (mod n).

Proof. Because ϕ is a bijection, there are integers r ∈ ℤ_{n_{1}} and s ∈ ℤ_{n_{2}} such that a_{1}r + a_{2}s ≡ n_{1}a_{1} (mod n). If r ≠ 0, then 0 ≤ n_{1} − r < n_{1}, and

a_{1}(n_{1} − r) ≡ a_{2}s (mod n).

Hence ϕ(n_{1} − r, 0) = ϕ(0, s), and this contradicts the assumption that ϕ is a bijection. Thus r = 0 and n_{1}a_{1} ≡ a_{2}s (mod n), as desired. □

Lemma 3.3. Suppose that ϕ is a linear bijection. Then either n_{1}a_{1} ≡ 0 (mod n) or n_{2}a_{2} ≡ 0 (mod n).

Proof. Set d = n_{2}/(a_{1}, n_{2}). By Lemma 3.2 there is an integer s ∈ ℤ_{n_{2}} such that n_{1}a_{1} ≡ a_{2}s (mod n), and it follows that da_{2}s ≡ dn_{1}a_{1} ≡ 0 (mod n). Hence n divides da_{2}s = n_{2}a_{2}s/(a_{1}, n_{2}), and n_{1}(a_{1}, n_{2}) divides a_{2}s. Thus

\frac{n_{1}}{(a_{2}, n_{1})} · (a_{1}, n_{2}) divides \frac{a_{2}}{(a_{2}, n_{1})} · s.

Now

(\frac{n_{1}}{(a_{2}, n_{1})}, \frac{a_{2}}{(a_{2}, n_{1})}) = 1;

moreover, the assumption that ϕ is a bijection implies that (a_{1}, a_{2}, n) = 1 and hence (a_{1}, n_{2}) is relatively prime to a_{2}/(a_{2}, n_{1}). Thus it follows that

(1)  \frac{n_{1}}{(a_{2}, n_{1})} · (a_{1}, n_{2}) divides s.

If we now apply Lemma 3.2 with ℤ_{n_{1}} and ℤ_{n_{2}} interchanged, we conclude that there is an element t ∈ ℤ_{n_{1}} such that n_{2}a_{2} ≡ a_{1}t (mod n). Applying the above argument to t instead of s, we see that

(2)  \frac{n_{2}}{(a_{1}, n_{2})} · (a_{2}, n_{1}) divides t.

Then (1) and (2) show that n_{1}n_{2} divides st. But 0 ≤ s ≤ n_{2} −1 and 0 ≤ t ≤ n_{1} −1, so either s = 0 or t = 0, and the result follows. □

Proof of Theorem 3.1. Suppose that ϕ is a linear bijection. Then by Lemma 3.3 we know that either n_{2} divides a_{1} or n_{1} divides a_{2}. We may assume without loss of generality that n_{2} divides a_{1}. Set

d = (n_{1}, \frac{a_{1}}{n_{2}} ) .

Then

a_{1} · \frac{n_{1}}{d} = \frac{a_{1}}{n_{2}d} · n_{1}n_{2} ≡ 0 (mod n).

If d > 1, then it follows that

ϕ(n_{1}/d, 0) = ϕ(0, 0),

and this contradicts the assumption that ϕ is a bijection. Thus d = 1, and we conclude that (a_{1}, n) = n_{2}. Because ϕ is a bijection, it follows that 1 = (a_{1}, a_{2}, n) = (a_{2}, n_{2}), as desired.

To prove the converse, we may assume that (a_{1}, n) = n_{2} and (a_{2}, n_{2}) = 1. Suppose that ϕ(j_{1}, j_{2}) = ϕ(j′_{1}, j′_{2}) so that

a_{1}j_{1} + a_{2}j_{2} ≡ a_{1}j′_{1} + a_{2}j′_{2} (mod n).

Because n_{2} divides a_{1}, it follows that

a_{2}j_{2} ≡ a_{2}j′_{2} (mod n_{2}).

Then the assumption that (a_{2}, n_{2}) = 1 implies that j_{2} = j′_{2}, so

a_{1}j_{1} ≡ a_{1}j′_{1} (mod n).

Because (a_{1}, n) = n_{2}, we can write a_{1} = n_{2}a′_{1} with (a′_{1}, n_{1}) = 1. Then the above congruence implies that

a′_{1}j_{1} ≡ a′_{1}j′_{1} (mod n_{1})

and hence j_{1} = j′_{1}. Thus ϕ is a bijection, and this completes the proof. □

Theorem 3.1 gives a natural division of the set B of all linear bijections from ℤ_{n_{1}} × ℤ_{n_{2}} to ℤ_{n} into two subsets. Let B_{1} denote the linear bijections that satisfy condition (1) of Theorem 3.1, and let B_{2} denote those that satisfy condition (2). The following corollary is an immediate consequence of Theorem 3.1, and the proof will be omitted.

Corollary 3.4. The set B is the union of B_{1} and B_{2}; moreover, if (n_{1}, n_{2}) ≠ 1, then B_{1} ∩ B_{2} = ∅.

Now consider the more general situation in which n = n_{1} ⋯ n_{t} for some natural numbers n_{1}, …, n_{t}. Let a_{1}, …, a_{t} be integers with 0 ≤ a_{s} ≤ n − 1 for 1 ≤ s ≤ t, and define ϕ : ℤ_{n_{1}} × ⋯ × ℤ_{n_{t}} → ℤ_{n} by

ϕ(j_{1}, …, j_{t}) = ⟨a_{1}j_{1} + ⋯ + a_{t}j_{t}⟩_{n}.

Conjecture 3.5. The function ϕ is a bijection if and only if it is possible to reorder the indices so that for 1 ≤ s ≤ t the coefficient a_{s} satisfies a_{s} = n_{1} ⋯ n_{s−1}a′_{s} for some natural number a′_{s} with (a′_{s}, n_{s}) = 1.

One can show by induction on t that if the coefficients a_{1}, …, a_{t} satisfy the given condition, then ϕ is a bijection. In addition, it is easy to see that Conjecture 3.5 is equivalent to Theorem 3.1 when t = 2. We have also verified the conjecture in the following cases:

(1) There is a prime p such that n_{1}, …, n_{t} are all powers of p.

(2) The numbers n_{1}, …, n_{t} are distinct primes and t ≤ 4.

4. Applications to the Discrete Fourier Transform

In this section we will develop a general framework for studying fast Fourier transform algorithms in terms of the linear bijections considered previously. In particular, we will characterize all possible bijections that lead to FFT algorithms and will single out a particular class of bijections that appear to have some computational advantages.

Fix n ∈ ℕ, and set i = \sqrt{−1} and ω_{n} = e^{−2πi/n}. Recall that the discrete Fourier transform maps an n-tuple (x_{0}, …, x_{n−1}) ∈ ℂ^{n} to another n-tuple (y_{0}, …, y_{n−1}) ∈ ℂ^{n} given by

(∗)  y_{k} = ∑_{j=0}^{n−1} ω_{n}^{kj}x_{j}

for 0 ≤ k ≤ n − 1. If the discrete Fourier transform is evaluated using this formula, then it requires O(n^{2}) complex multiplications and additions.

On the other hand, if n can be factored as n = n_{1}n_{2} with n_{1}, n_{2} > 1, then the number of floating point operations can be drastically reduced. In the case of the algorithm suggested by Cooley and Tukey [6], for example, this reduction is based upon choosing two linear bijections ϕ, ψ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} given by

ϕ(j_{1}, j_{2}) = j_{1} + n_{1}j_{2}

and

ψ(k_{1}, k_{2}) = n_{2}k_{1} + k_{2}.

Setting j = ϕ(j_{1}, j_{2}) and k = ψ(k_{1}, k_{2}), we get

ω_{n}^{kj} = ω_{n}^{(n_{2}k_{1}+k_{2})(j_{1}+n_{1}j_{2})} = ω_{n_{1}}^{k_{1}j_{1}}ω_{n}^{k_{2}j_{1}}ω_{n_{2}}^{k_{2}j_{2}},

and it is possible to split the sum in (∗) into a double sum:

y_{n_{2}k_{1}+k_{2}} = ∑_{j_{1}=0}^{n_{1}−1} ω_{n_{1}}^{k_{1}j_{1}}ω_{n}^{k_{2}j_{1}} ∑_{j_{2}=0}^{n_{2}−1} ω_{n_{2}}^{k_{2}j_{2}}x_{j_{1}+n_{1}j_{2}}.

This formula can now be used to evaluate the discrete Fourier transform in four steps:

(1) Compute n_{1} transforms of order n_{2}:

u_{j_{1}+n_{1}k_{2}} = ∑_{j_{2}=0}^{n_{2}−1} ω_{n_{2}}^{k_{2}j_{2}}x_{j_{1}+n_{1}j_{2}};

(2) Multiply by the twiddle factors:

v_{j_{1}+n_{1}k_{2}} = ω_{n}^{k_{2}j_{1}}u_{j_{1}+n_{1}k_{2}};

(3) Permute the data:

z_{n_{2}j_{1}+k_{2}} = v_{j_{1}+n_{1}k_{2}};

(4) Compute n_{2} transforms of order n_{1}:

y_{n_{2}k_{1}+k_{2}} = ∑_{j_{1}=0}^{n_{1}−1} ω_{n_{1}}^{k_{1}j_{1}}z_{n_{2}j_{1}+k_{2}}.

Note that this procedure involves only O(n(n_{1}+n_{2}+1)) complex multiplications. When n is highly composite, the idea can be applied recursively in steps (1) and (4), and the floating point operation count is reduced to O(n log n). If recursion is applied in only the first step of the procedure, then the resulting algorithm is called decimation in time; if recursion is applied in only the last step, then the algorithm is called decimation in frequency. The reason for this terminology is that in applications the array x is often a time signal, whereas y is a frequency signal. If the factors n_{1} and n_{2} are chosen to be of about the same size, then decimation both in time and frequency is possible, and a new algorithm of this kind with many desirable properties has been proposed in [8, 10]. A systematic study of all possible variants of such algorithms was carried out in [7]. An application to parallel processing has been suggested in [12], and the idea was further exploited for real Fourier transforms in [9].

The Cooley–Tukey algorithm begins by choosing two very specific linear bijections for the indices j and k. To generalize this idea, suppose that ϕ, ψ : ℤ_{n_{1}}×ℤ_{n_{2}} → ℤ_{n} are linear bijections given by and

ψ(k_{1}, k_{2}) = ⟨b_{1}k_{1} + b_{2}k_{2}⟩_{n}.

If j = ϕ(j_{1}, j_{2}) and k = ψ(k_{1}, k_{2}), then

kj ≡ b_{1}a_{1}k_{1}j_{1} + b_{2}a_{1}k_{2}j_{1} + b_{1}a_{2}k_{1}j_{2} + b_{2}a_{2}k_{2}j_{2} (mod n).

Whether the pair of bijections (ϕ, ψ) leads to an FFT algorithm depends upon the form of the product kj. Specifically, if either b_{2}a_{1} ≡ 0 (mod n) or b_{1}a_{2} ≡ 0 (mod n), then the pair (ϕ, ψ) will determine a corresponding Fourier transform algorithm analogous to the one described previously. For example, suppose that b_{2}a_{1} ≡ 0 (mod n). Then

ω_{n}^{kj} = (ω_{n}^{b_{1}a_{1}})^{k_{1}j_{1}} (ω_{n}^{b_{1}a_{2}})^{k_{1}j_{2}} (ω_{n}^{b_{2}a_{2}})^{k_{2}j_{2}} ,

and the Fourier transform can be calculated by a double sum given by the formula

y_{⟨b_{1}k_{1}+b_{2}k_{2}⟩_{n}} = ∑_{j_{2}=0}^{n_{2}−1} (ω_{n}^{b_{2}a_{2}})^{k_{2}j_{2}} (ω_{n}^{b_{1}a_{2}})^{k_{1}j_{2}} ∑_{j_{1}=0}^{n_{1}−1} (ω_{n}^{b_{1}a_{1}})^{k_{1}j_{1}} x_{⟨a_{1}j_{1}+a_{2}j_{2}⟩_{n}}.

This double sum can be processed in four steps, as in the case of the Cooley-Tukey algorithm. Moreover, the first and last steps involve computing a (rotated) discrete Fourier transform.

If n_{1} is a multiple of n_{2} or n_{2} is a multiple of n_{1}, then it is also possible to choose ϕ and ψ so that either b_{1}a_{1} ≡ 0 (mod n) or b_{2}a_{2} ≡ 0 (mod n), and these cases lead to a nonstandard way of calculating the discrete Fourier transform. This idea does not appear to be useful for computational purposes, however, and it will not be investigated here.

Because the pair of linear bijections (ϕ, ψ) leads to a fast Fourier transform algorithm if and only if either b_{2}a_{1} ≡ 0 (mod n) or b_{1}a_{2} ≡ 0 (mod n), it will be useful to single out this situation. We refer to such a pair (ϕ, ψ) as a splitting pair. The following lemma gives one possible way to characterize splitting pairs.

Lemma 4.1. Let ϕ, ψ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} be linear bijections given by ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1} + a_{2}j_{2}⟩_{n} and ψ(k_{1}, k_{2}) = ⟨b_{1}k_{1} + b_{2}k_{2}⟩_{n}. Then

(1) b_{2}a_{1} ≡ 0 (mod n) if and only if there are integers a′_{s} and b′_{s} such that (a′_{s}, n_{s}) = (b′_{s}, n_{s}) = 1 for s = 1, 2 and a_{1} = n_{2}a′_{1}, a_{2} = a′_{2}, b_{1} = b′_{1}, b_{2} = n_{1}b′_{2}.

(2) b_{1}a_{2} ≡ 0 (mod n) if and only if there are integers a′_{s} and b′_{s} such that (a′_{s}, n_{s}) = (b′_{s}, n_{s}) = 1 for s = 1, 2 and a_{1} = a′_{1}, a_{2} = n_{1}a′_{2}, b_{1} = n_{2}b′_{1}, b_{2} = b′_{2}.

Proof. By symmetry it suffices to prove (1). If there are integers a′_{s} and b′_{s} satisfying the given conditions, then clearly b_{2}a_{1} ≡ 0 (mod n). Conversely, suppose that b_{2}a_{1} ≡ 0 (mod n). Because ϕ is a linear bijection, Theorem 3.1 implies that one of the following conditions is satisfied:

i) (a_{1}, n) = n_{2} and (a_{2}, n_{2}) = 1.

ii) (a_{2}, n) = n_{1} and (a_{1}, n_{1}) = 1.

If i) holds, then b_{2} ≡ 0 (mod n_{1}) because b_{2}a_{1} ≡ 0 (mod n) and (a_{1}, n) = n_{2}; if ii) holds, then b_{2} ≡ 0 (mod n_{1}) because b_{2}a_{1} ≡ 0 (mod n) and (a_{1}, n_{1}) = 1. Thus in either case n_{1} divides b_{2}, and there is an integer b′_{2} such that b_{2} = n_{1}b′_{2}. If (b′_{2}, n_{2}) ≠ 1, then (b_{2}, n) > n_{1} and Theorem 3.1 implies that (b_{2}, n_{2}) = 1. Since this contradicts the assumption that (b′_{2}, n_{2}) ≠ 1, we conclude that (b′_{2}, n_{2}) = 1 and hence (b_{2}, n) = n_{1}. Moreover, because ψ is a linear bijection, it follows that (b_{1}, b_{2}, n) = 1 so that (b_{1}, n_{1}) = 1. A similar argument shows that there is an integer a′_{1} such that a_{1} = n_{2}a′_{1} and (a′_{1}, n_{1}) = (a_{2}, n_{2}) = 1, and this completes the proof. □

We can now give another description of splitting pairs in terms of the sets of bijections B_{1} and B_{2} defined in Section 3. The following proposition is an immediate consequence of Lemma 4.1.

Proposition 4.2. Let ϕ, ψ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} be linear bijections. Then (ϕ, ψ) is a splitting pair if and only if (ϕ, ψ) ∈ (B_{1} × B_{2}) ∪ (B_{2} × B_{1}).

As we observed previously, a pair (ϕ, ψ) satisfying either b_{2}a_{1} ≡ 0 (mod n) or b_{1}a_{2} ≡ 0 (mod n) will lead to a fast Fourier transform algorithm. A particularly interesting case arises when both congruences hold. Then

ω_{n}^{kj} = (ω_{n}^{b_{1}a_{1}})^{k_{1}j_{1}} (ω_{n}^{b_{2}a_{2}})^{k_{2}j_{2}} ,

and multiplication by a twiddle factor is unnecessary. A pair (ϕ, ψ) such that b_{2}a_{1} ≡ b_{1}a_{2} ≡ 0 (mod n) will be called a prime splitting pair because this situation can arise only if n_{1} and n_{2} are relatively prime, as the next result shows. The proposition follows easily from Lemma 4.1 and Theorem 3.1.

Proposition 4.3. Let ϕ, ψ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} be linear bijections with ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1} + a_{2}j_{2}⟩_{n} and ψ(k_{1}, k_{2}) = ⟨b_{1}k_{1} + b_{2}k_{2}⟩_{n}. Then the following statements are equivalent:

(1) (ϕ, ψ) is a prime splitting pair.

(2) (ϕ, ψ) ∈ (B_{1} ∩ B_{2}) × (B_{1} ∩ B_{2}).

(3) There are integers a′_{s} and b′_{s} such that (a′_{s}, n_{s}) = (b′_{s}, n_{s}) = 1 for s = 1, 2

and a_{1} = n_{2}a′_{1}, a_{2} = n_{1}a′_{2}, b_{1} = n_{2}b′_{1}, b_{2} = n_{1}b′_{2}. Moreover, if these conditions are satisfied, then (n_{1}, n_{2}) = 1.

In the situation described by Proposition 4.3 one possibility is to take a_{1} = b_{1} = n_{2} and a_{2} = b_{2} = n_{1}; then ϕ = ψ is the inverse of the Ruritanian mapping. If s_{1} ∈ ℤ_{n_{2}} and s_{2} ∈ ℤ_{n_{1}} are the integers such that s_{1}n_{1} ≡ 1 (mod n_{2}) and s_{2}n_{2} ≡ 1 (mod n_{1}), then one could also take a_{1} = b_{1} = n_{2}s_{2} and a_{2} = b_{2} = n_{1}s_{1}; this case is related to the Chinese Remainder Theorem. A combination of these two possibilities arises by taking a_{1} = n_{2}, a_{2} = n_{1}, b_{1} = n_{2}s_{2}, and b_{2} = n_{1}s_{1}. This situation is called prime factor splitting in [13].

The main advantage of prime splitting pairs is that no twiddle factors have to be computed in the resulting FFT algorithm; but only relatively prime factors n_{1} and n_{2} admit such pairs. We will now suggest a way to extend this advantage by reducing the number of twiddle factor computations when n_{1} and n_{2} are not relatively prime. Let m_{1} be the largest factor of n_{1} such that (m_{1}, n_{2}) = 1, and let m_{2} be the largest factor of n_{2} such that (m_{2}, n_{1}) = 1. We will say that (ϕ, ψ) is a maximal splitting pair if at least one of the following conditions is satisfied:

(1) b_{2}a_{1} ≡ 0 (mod n) and b_{1}a_{2} ≡ 0 (mod m_{1}m_{2}).

(2) b_{1}a_{2} ≡ 0 (mod n) and b_{2}a_{1} ≡ 0 (mod m_{1}m_{2}). Note that if (n_{1}, n_{2}) = 1, then a maximal splitting pair is the same as a prime splitting pair; and if m_{1} = m_{2} = 1, then the Cooley-Tukey pair is maximal.

The next lemma gives a more explicit description of maximal splitting pairs. The proof is similar to that of Lemma 4.1 and will be omitted.

Lemma 4.4. Suppose that ϕ, ψ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} are linear bijections given by ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1} + a_{2}j_{2}⟩_{n} and ψ(k_{1}, k_{2}) = ⟨b_{1}k_{1} + b_{2}k_{2}⟩_{n}. Let m_{1} be the largest factor of n_{1} such that (m_{1}, n_{2}) = 1, and let m_{2} be the largest factor of n_{2} such that (m_{2}, n_{1}) = 1. Then

(1) b_{2}a_{1} ≡ 0 (mod n) and b_{1}a_{2} ≡ 0 (mod m_{1}m_{2}) if and only if there are integers a′_{s} and b′_{s} such that (a′_{s}, n_{s}) = (b′_{s}, n_{s}) = 1 for s = 1, 2 and a_{1} = n_{2}a′_{1}, a_{2} = m_{1}a′_{2}, b_{1} = m_{2}b′_{1}, b_{2} = n_{1}b′_{2}.

(2) b_{1}a_{2} ≡ 0 (mod n) and b_{2}a_{1} ≡ 0 (mod m_{1}m_{2}) if and only if there are integers a′_{s} and b′_{s} such that (a′_{s}, n_{s}) = (b′_{s}, n_{s}) = 1 for s = 1, 2 and a_{1} = m_{2}a′_{1}, a_{2} = n_{1}a′_{2}, b_{1} = n_{2}b′_{1}, b_{2} = m_{1}b′_{2}.

We now want to state a result for maximal splitting pairs analogous to Proposition 4.2. Suppose that ϕ ∈ B_{1} is a linear bijection given by ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1}+a_{2}j_{2}⟩_{n}. Then (a_{2}, n_{2}) = 1, so it follows that (a_{2}, n_{1}) is a factor of n_{1} that is relatively prime to n_{2} and hence (a_{2}, n_{1}) divides m_{1}. Similarly, if ψ ∈ B_{2} is a linear bijection given by ψ(k_{1}, k_{2}) = ⟨b_{1}k_{1} + b_{2}k_{2}⟩_{n}, then (b_{1}, n_{2}) divides m_{2}. Let M_{1} denote the subset of B_{1} consisting of those linear bijections ϕ for which (a_{2}, n_{1}) = m_{1}, and let M_{2} denote the subset of B_{2} consisting of those linear bijections ψ for which (b_{1}, n_{2}) = m_{2}. The following result is now an easy consequence of Lemma 4.4.

Proposition 4.5. Let ϕ, ψ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} be linear bijections. Then (ϕ, ψ) is a maximal splitting pair if and only if (ϕ, ψ) ∈ (M_{1} × M_{2}) ∪ (M_{2} × M_{1}).

The computational implementation of FFT algorithms is often done in two parts. The first (precomputational) part involves computing and storing tables containing sines and cosines calculated on an equidistant grid on [0, 2π], and the second part uses these stored values to compute the discrete Fourier transform. Although the first part is always an essential step in the algorithm, it is sometimes omitted when evaluating the complexity. But computing the sine and cosine tables is expensive. For example, a Fourier transform of size n = 2^{20} requires 100n additions and multiplications in the second part of the algorithm. If each trigonometric function can be evaluated in the time taken for ten floating point operations, then computing n sines and n cosines would take the same amount of time as 20n additions and multiplications. In this case, then, the first part of the FFT algorithm would take roughly 20 percent of the time needed for the second part. This estimate has been confirmed in practical tests in which symmetries of the trigonometric functions were used extensively and additions and multiplications of the evaluation were partly overlapped. Moreover, if parallel computers are used, then each processor needs its own trigonometric table so that redundant computations are needed in order to avoid communication between the processors. It should also be noted that most rounding errors in FFT algorithms originate from the trigonometric functions, so great care is required in computing them [13].

It is desirable, then, to reduce as far as possible the number of twiddle factors that must be computed. The point of choosing the splitting pair to be maximal is that in this case only powers of ω_{n/m_{1}m_{2}} arise as twiddle factors. We believe that the resulting maximal splitting pair (MSP) algorithm has the greatest advantages for parallel computing.

The four-step method discussed previously for calculating the discrete Fourier transform lends itself quite naturally to parallel implementation. The data is distributed so that each processor can do the first and last step without communication. If the appropriate values of trigonometric functions are available, then it is also unnecessary to exchange data in step (2). Thus all the communication occurs in step (3), which involves so-called personalized all-to-all communication. The degree of parallelism exploited is n_{1} in step (1) and n_{2} in step (4). In order to use massively parallel computers, it is best for n_{1} and n_{2} to be of the same order. The maximal splitting pair algorithm allows for this type of balancing while maintaining a low level of calculation in the precomputational step.

For example, suppose that n = 162, 000 = 2^{4} · 3^{4} · 5^{3}. Then the prime factor algorithm would result from the factorizations n_{1} = 16 and n_{2} = 10, 125; or n_{1} = 81 and n_{2} = 2000; or n_{1} = 125 and n_{2} = 1296. A more balanced factorization is given by taking n_{1} = 405 and n_{2} = 400. If the Cooley–Tukey algorithm is used in this case, then a trigonometric table of full size n = 162, 000 is needed. For the MSP algorithm, on the other hand, the first step requires a table of size 125, and the later steps require tables of size at most 81.

A natural class of problems that is hardly discussed in the literature involves transforms in which the order is a power of 10. For example, suppose that n = 10^{6}. Then the factorization n_{1} = n_{2} = 1000 allows for the greatest degree of parallelism. In this case, however, the Cooley–Tukey algorithm requires a trigonometric table of size 10^{6}. If the prime factor algorithm is used with n_{1} = 64 and n_{2} = 15, 625, then the largest table that is eventually needed has size 15,625, but the maximal parallelism is only 64. A somewhat more balanced choice would be n_{1} = 625 and n_{2} = 1600. The resulting MSP algorithm again requires a table of size 15,625, but here it is used in the first step. In this case, then, the MSP algorithm combines some of the advantages of the prime factor algorithm with those of the Cooley–Tukey algorithm.

5. Addition in ℤ_{n}

In this section we begin to study the relationships between linear bijections and the additive structure on the group ℤ_{n}. To motivate the discussion, consider the example in which n = 100 and n_{1} = n_{2} = 10. Suppose that the linear bijection ϕ : ℤ_{10} × ℤ_{10} → ℤ_{100} is given by

ϕ(j_{1}, j_{2}) = ⟨10j_{1} + j_{2}⟩_{100},

and set j = ϕ(j_{1}, j_{2}). Then j_{1} and j_{2} are nothing more than the digits in the usual representation of j as a two-digit number in ℤ_{100}. If h ∈ ℤ_{100} with h = ϕ(h_{1}, h_{2}), then the sum j + h in ℤ_{100} satisfies

⟨j + h⟩_{100} = ⟨10(j_{1} + h_{1}) + (j_{2} + h_{2})⟩_{100}.

We want to rewrite this expression as ϕ(j′_{1}, j′_{2}) for some j′_{1}, j′_{2} ∈ ℤ_{10}, but it may be necessary to carry from the ones digit to the tens digit when performing the addition. Let f : ℤ_{10} × ℤ_{10} → ℤ_{10} be the function describing the number carried; then f is given by

f(j_{2}, h_{2}) = \{ \begin{matrix}1 & if j_{2} + h_{2} ≥ 10 \\ 0 & if j_{2} + h_{2} < 10. \end{matrix}

It follows that

⟨ϕ(j_{1}, j_{2}) + ϕ(h_{1}, h_{2})⟩_{100} = ⟨j + h⟩_{100}
= 10⟨j_{1} + h_{1} + f(j_{2}, h_{2})⟩_{10} + ⟨j_{2} + h_{2}⟩_{10}
= ϕ(⟨j_{1} + h_{1} + f(j_{2}, h_{2})⟩_{10}, ⟨j_{2} + h_{2}⟩_{10}).

More generally, suppose that ϕ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} is a linear bijection given by

ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1} + a_{2}j_{2}⟩_{n}.

By interchanging the factors n_{1} and n_{2} if necessary, we may assume that condition (1) of Theorem 3.1 is satisfied. Then (a_{2}, n_{2}) = 1, and there is an integer a′_{1} such that a_{1} = n_{2}a′_{1} and (a′_{1}, n_{1}) = 1. Let c_{1} ∈ ℤ_{n_{1}} be the integer such that a′_{1}c_{1} ≡ 1 (mod n_{1}), and define f : ℤ_{n_{2}} × ℤ_{n_{2}} → ℤ_{n_{1}} by

f(j_{2}, h_{2}) = \{ \begin{matrix}⟨a_{2}c_{1}⟩_{n_{1}} & if j_{2} + h_{2} ≥ n_{2} \\ 0 & if j_{2} + h_{2} < n_{2}. \end{matrix}

Then one can check that the addition in ℤ_{n} satisfies

⟨ϕ(j_{1}, j_{2}) + ϕ(h_{1}, h_{2})⟩_{n} = ⟨a_{1}(j_{1} + h_{1}) + a_{2}(j_{2} + h_{2})⟩_{n}
= ⟨n_{2}a′_{1}⟨j_{1} + h_{1} + f(j_{2}, h_{2})⟩_{n_{1}} + a_{2}⟨j_{2} + h_{2}⟩_{n_{2}}⟩_{n}
= ϕ(⟨j_{1} + h_{1} + f(j_{2}, h_{2})⟩_{n_{1}}, ⟨j_{2} + h_{2}⟩_{n_{2}}).

In other words, if j ∈ ℤ_{n} and j = ϕ(j_{1}, j_{2}), then we can think of j_{1} and j_{2} as the digits of j. It is then possible to add elements of ℤ_{n} by adding the digits as usual; the only difference is that instead of carrying a 1, it is now necessary to carry ⟨a_{2}c_{1}⟩_{n_{1}}. We will therefore refer to f as the carry function.

Note that in the case of the prime splitting pairs described in Proposition 4.3 the linear bijection ϕ is given by ϕ(j_{1}, j_{2}) = ⟨n_{2}a′_{1}j_{1} +n_{1}a′_{2}j_{2}⟩_{n}. Because a_{2} = n_{1}a′_{2} is always a multiple of n_{1}, the addition formula simplifies:

⟨ϕ(j_{1}, j_{2}) + ϕ(h_{1}, h_{2})⟩_{n} = ϕ(⟨j_{1} + h_{1}⟩_{n_{1}}, ⟨j_{2} + h_{2}⟩_{n_{2}}).

Thus carrying is unnecessary, and the addition of both digits could be done in parallel.

6. Group Extensions and 2-cocycles

In the previous section we saw that every linear bijection ϕ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} satisfying condition (1) of Theorem 3.1 determines a corresponding carry function f : ℤ_{n_{2}} × ℤ_{n_{2}} → ℤ_{n_{1}}. In this section we consider the relationship between ϕ and f more carefully. One natural question that arises, for example, is whether the carry function in turn determines the linear bijection. We will see that this is not the case, although f does determine ϕ modulo a certain equivalence relation.

The idea used here is to relate linear bijections and carry functions to group extensions, and the starting point is the observation that carry functions provide examples of 2-cocycles. If n_{1}, n_{2} ∈ ℕ, then a 2-cocycle (or factor set) from ℤ_{n_{2}} to ℤ_{n_{1}} is a function f : ℤ_{n_{2}} × ℤ_{n_{2}} → ℤ_{n_{1}} satisfying

⟨f(⟨h + j⟩_{n_{2}}, k) + f(h, j)⟩_{n_{1}} = ⟨f(h, ⟨j + k⟩_{n_{2}}) + f(j, k)⟩_{n_{1}} (1) f(h, j) = f(j, h) (2)

for all h, j, k ∈ ℤ_{n_{2}}. If f(0, 0) = 0, then f is said to be normalized. We will consider only normalized 2-cocycles.

Every 2-cocycle f from ℤ_{n_{2}} to ℤ_{n_{1}} determines a corresponding extension of ℤ_{n_{1}} by ℤ_{n_{2}}. Thus there is an abelian group A and a short exact sequence

E :  0 ⟶ ℤ_{n_{1}} ⟶^{μ} A ⟶^{ν} ℤ_{n_{2}} ⟶ 0;

in other words, μ is a monomorphism, ν is an epimorphism, and Im μ = Ker ν. We can construct the abelian group A explicitly by taking A to be the set of all pairs [j_{1}, j_{2}] ∈ ℤ_{n_{1}} × ℤ_{n_{2}}, with the addition in A given by

[j_{1}, j_{2}] + [h_{1}, h_{2}] = [⟨j_{1} + h_{1} + f(j_{2}, h_{2})⟩_{n_{1}}, ⟨j_{2} + h_{2}⟩_{n_{2}}].

The cocycle condition (1) is necessary to ensure that this addition is an associative operation, while (2) ensures that it is commutative. The maps μ : ℤ_{n_{1}} → A and ν : A → ℤ_{n_{2}} are given explicitly by

μ(j) = [j, 0]  and  ν[j_{1}, j_{2}] = j_{2}.

Now suppose that for s = 1, 2 we have extensions

E_{s} :  0 ⟶ ℤ_{n_{1}} ⟶^{μ_{s}} A_{s} ⟶^{ν_{s}} ℤ_{n_{2}} ⟶ 0

of ℤ_{n_{1}} by ℤ_{n_{2}}. We write E_{1} ≡ E_{2} and say that the extensions E_{1} and E_{2} are equivalent (or isomorphic) if there is a group homomorphism γ : A_{1} → A_{2} such that γμ_{1} = μ_{2} and ν_{2}γ = ν_{1}. We can also express this idea by saying that there is a commutative diagram

0 ⟶ ℤ_{n_{1}} ⟶^{μ_{1}} A_{1} ⟶^{ν_{1}} ℤ_{n_{2}} ⟶ 0
∥  ↓^{γ}  ∥
0 ⟶ ℤ_{n_{1}} ⟶_{μ_{2}} A_{2} ⟶_{ν_{2}} ℤ_{n_{2}} ⟶ 0.

Any such homomorphism γ must necessarily be an isomorphism.

If m ∈ ℕ and A is an abelian group, then any homomorphism μ : ℤ_{m} → A is uniquely determined by specifying the element a = μ(1) ∈ A. In this situation the map μ is given by multiplication by a, and we will often find it convenient to write the homomorphism simply as a : ℤ_{m} → A.

Now suppose that u : ℤ_{n_{2}} → ℤ_{n_{1}} is any function with u(0) = 0. Then the function δu : ℤ_{n_{2}} × ℤ_{n_{2}} → ℤ_{n_{1}} defined by

(δu)(j, h) = ⟨u(j) + u(h) − u(⟨j + h⟩_{n_{2}})⟩_{n_{1}}

is called the coboundary of u. Every coboundary is also a cocycle. Let f_{1} and f_{2} be 2-cocycles, and let E_{1} and E_{2} be the corresponding extensions of ℤ_{n_{1}} by ℤ_{n_{2}}. Then E_{1} ≡ E_{2} if and only if ⟨f_{1} − f_{2}⟩_{n_{1}} is a coboundary. A good reference for further information on cocycles, coboundaries, and extensions is [11].

We now fix some notation for the remainder of this section. If c ∈ ℤ, define f_{c} : ℤ_{n_{2}} × ℤ_{n_{2}} → ℤ_{n_{1}} by

f_{c}(j, h) = \{ \begin{matrix}⟨c⟩_{n_{1}} & if j + h ≥ n_{2} \\ 0 & if j + h < n_{2} \end{matrix}

for all j, h ∈ ℤ_{n_{2}}. We also set d = (n_{1}, n_{2}), and we continue to assume that n = n_{1}n_{2} as in the previous sections.

The following lemma is easy to verify, and the proof is left to the reader. In effect, it says that all carry functions are 2-cocycles.

Lemma 6.1. The function f_{c} : ℤ_{n_{2}} × ℤ_{n_{2}} → ℤ_{n_{1}} is a 2-cocycle for all c ∈ ℤ.

Proposition 6.2. Let c ∈ ℤ such that (c, d) = 1, and factor c as c = αβ with (α, n_{1}) = (β, n_{2}) = 1. Let a ∈ ℤ_{n_{1}} and b ∈ ℤ_{n_{2}} be integers such that αa ≡ 1 (mod n_{1}) and βb ≡ 1 (mod n_{2}). Then the extension corresponding to the 2-cocycle f_{c} is isomorphic to

0 ⟶ ℤ_{n_{1}} ⟶^{n_{2}a} ℤ_{n} ⟶^{b} ℤ_{n_{2}} ⟶ 0.

Proof. Let A be the extension of ℤ_{n_{1}} by ℤ_{n_{2}} corresponding to f_{c}. We may assume that A = ℤ_{n_{1}} × ℤ_{n_{2}} as a set, with the addition given by

[j_{1}, j_{2}] + [h_{1}, h_{2}] = [⟨j_{1} + h_{1} + f_{c}(j_{2}, h_{2})⟩_{n_{1}}, ⟨j_{2} + h_{2}⟩_{n_{2}}].

Because βb ≡ 1 (mod n_{2}), the number t = (1 − βb)/n_{2} is an integer. We begin by showing that the element [⟨tα⟩_{n_{1}}, b] ∈ A has order n.

First note that if m ∈ ℕ such that m[⟨tα⟩_{n_{1}}, b] = 0, then mb ≡ 0 (mod n_{2}). Because βb ≡ 1 (mod n_{2}), it follows that n_{2} divides m. Thus we must show that n_{2}[⟨tα⟩_{n_{1}}, b] has order n_{1}. It is easy to check by induction that for s ≥ 1,

s[⟨tα⟩_{n_{1}}, b] = [⟨stα + ∑_{u=1}^{s−1} f_{c}(b, ⟨ub⟩_{n_{2}})⟩_{n_{1}}, ⟨sb⟩_{n_{2}}] .

Taking s = n_{2}, we get

n_{2}[⟨tα⟩_{n_{1}}, b] = [⟨n_{2}tα + ∑_{u=1}^{n_{2}−1} f_{c}(b, ⟨ub⟩_{n_{2}})⟩_{n_{1}}, 0] .

Thus it suffices to show that the element of ℤ_{n_{1}} given by

⟨n_{2}tα + ∑_{u=1}^{n_{2}−1} f_{c}(b, ⟨ub⟩_{n_{2}})⟩_{n_{1}}

has order n_{1}. One can check by induction on m that if s is the natural number such that sn_{2} ≤ mb < (s + 1)n_{2}, then

∑_{u=1}^{m−1} f_{c}(b, ⟨ub⟩_{n_{2}}) ≡ sc (mod n_{1}).

Thus it follows that

n_{2}tα + ∑_{u=1}^{n_{2}−1} f_{c}(b, ⟨ub⟩_{n_{2}}) ≡ n_{2}tα + bc = α(n_{2}t + βb) = α (mod n_{1}).

But (α, n_{1}) = 1, so [⟨tα⟩_{n_{1}}, b] is an element of A of order n, as claimed. In particular, we see that A is a cyclic group of order n.

Let γ : ℤ_{n} → A be the unique group homomorphism satisfying

γ(1) = [⟨tα⟩_{n_{1}}, b].

Then

γ(n_{2}a) = an_{2}[⟨tα⟩_{n_{1}}, b]
= a[⟨α⟩_{n_{1}}, 0]
= [⟨αa⟩_{n_{1}}, 0]
= [1, 0].

Thus γ defines an isomorphism of group extensions

0 ⟶ ℤ_{n_{1}} ⟶^{n_{2}a} ℤ_{n} ⟶^{b} ℤ_{n_{2}} ⟶ 0
∥  ↓^{γ}  ∥
0 ⟶ ℤ_{n_{1}} ⟶ A ⟶ ℤ_{n_{2}} ⟶ 0,

and this completes the proof. □

Proposition 6.3. For s = 1, 2 let c_{s} ∈ ℤ such that (c_{s}, d) = 1, and let E_{s} be the extension of ℤ_{n_{1}} by ℤ_{n_{2}} determined by the 2-cocycle f_{c_{s}}. Then E_{1} ≡ E_{2} if and only if c_{1} ≡ c_{2} (mod d).

Proof. Write c_{s} = α_{s}β_{s} with (α_{s}, n_{1}) = (β_{s}, n_{2}) = 1. Let a_{s} ∈ ℤ_{n_{1}} and b_{s} ∈ ℤ_{n_{2}} be integers such that α_{s}a_{s} ≡ 1 (mod n_{1}) and β_{s}b_{s} ≡ 1 (mod n_{2}). By Proposition 6.2 we may assume that E_{s} is given by

E_{s} :  0 ⟶ ℤ_{n_{1}} ⟶^{n_{2}a_{s}} ℤ_{n} ⟶^{b_{s}} ℤ_{n_{2}} ⟶ 0.

Then E_{1} ≡ E_{2} if and only if there is an integer t such that the following diagram commutes:

(1)  \begin{aligned}0 & ⟶ & ℤ_{n_{1}} & ⟶^{n_{2}a_{1}} & ℤ_{n} & ⟶^{b_{1}} & ℤ_{n_{2}} & ⟶ & 0 \\ & & ∥ & & ↓^{t} & & ∥ \\ 0 & ⟶ & ℤ_{n_{1}} & ⟶_{n_{2}a_{2}} & ℤ_{n} & ⟶_{b_{2}} & ℤ_{n_{2}} & ⟶ & 0. \end{aligned}

Suppose that we have such a diagram. Then multiplication by t is an automorphism of ℤ_{n}, so (t, n) = 1. Moreover, n_{2}a_{2} ≡ tn_{2}a_{1} (mod n) and b_{1} ≡ b_{2}t (mod n_{2}). Hence a_{2} ≡ ta_{1} (mod n_{1}). Because (t, n) = 1, there is an integer u such that tu ≡ 1 (mod n). It follows that

a_{1}b_{1} ≡ (ua_{2})(b_{2}t) ≡ a_{2}b_{2} (mod d)

and hence

c_{1} = α_{1}β_{1} ≡ α_{2}β_{2} = c_{2} (mod d).

Conversely, suppose that c_{1} ≡ c_{2} (mod d). Then

α_{1}a_{2} ≡ α_{1}β_{1}b_{1}a_{2} = c_{1}b_{1}a_{2} ≡ c_{2}b_{1}a_{2} = α_{2}β_{2}b_{1}a_{2} ≡ β_{2}b_{1} (mod d).

By the Chinese Remainder Theorem it follows that the system of congruences

t ≡ α_{1}a_{2} (mod n_{1})
t ≡ β_{2}b_{1} (mod n_{2})

has a solution for some integer t. Then n_{2}a_{1}t ≡ n_{2}a_{2} (mod n) and b_{2}t ≡ b_{1} (mod n_{2}), so we get a diagram of the form given in (1). Hence E_{1} ≡ E_{2}, as desired. □

Proposition 6.4. Let E be an extension of the form

E :  0 ⟶ ℤ_{n_{1}} ⟶^{μ} ℤ_{n} ⟶^{ν} ℤ_{n_{2}} ⟶ 0.

Then there is an integer c such that 0 ≤ c ≤ d − 1, (c, d) = 1, and f_{c} is a 2-cocycle corresponding to the extension E.

Proof. First note that the maps μ and ν must satisfy μ(j) = ⟨n_{2}aj⟩_{n} and ν(j) = ⟨bj⟩_{n_{2}} for some integers a ∈ ℤ_{n_{1}} and b ∈ ℤ_{n_{2}}. Moreover, (a, n_{1}) = 1 because μ is one-to-one, and (b, n_{2}) = 1 because ν is onto. Let α ∈ ℤ_{n_{1}} and β ∈ ℤ_{n_{2}} be integers such that aα ≡ 1 (mod n_{1}) and bβ ≡ 1 (mod n_{2}), and set γ = αβ. Then (γ, d) = 1, and Proposition 6.2 implies that f_{γ} is a 2-cocycle corresponding to E.

Because (γ, d) = 1, there is an integer c with 0 ≤ c ≤ d − 1, (c, d) = 1, and c ≡ γ (mod d). It follows that there are integers s and t such that c − γ = sn_{1} + tn_{2}. Define u : ℤ_{n_{2}} → ℤ_{n_{1}} by setting u(j) = ⟨tj⟩_{n_{1}}. It is easy to check that if j, h ∈ ℤ_{n_{2}}, then

(δu)(j, h) = ⟨u(j) + u(h) − u(⟨j + h⟩_{n_{2}})⟩_{n_{1}}
= ⟨f_{c}(j, h) − f_{γ}(j, h)⟩_{n_{1}}.

Hence f_{c} and f_{γ} differ by a coboundary. Because f_{γ} corresponds to the extension E, it follows that f_{c} also corresponds to E. □

The previous results can be summarized as follows.

Theorem 6.5. There is a one-to-one correspondence between isomorphism classes of extensions of the form

0 ⟶ ℤ_{n_{1}} ⟶ ℤ_{n} ⟶ ℤ_{n_{2}} ⟶ 0

and integers c such that 0 ≤ c ≤ d − 1 and (c, d) = 1. The extension corresponding to the number c is that determined by the 2-cocycle f_{c}.

We now wish to relate Theorem 6.5 to the linear bijections studied in Section 3. Consider the collection B of all bijections ϕ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} of the form

ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1} + a_{2}j_{2}⟩_{n}

for some a_{1}, a_{2} ∈ ℤ_{n}, and recall that B_{1} denotes the subset consisting of those bijections that satisfy condition (1) of Theorem 3.1. Thus ϕ ∈ B_{1} if and only if (a_{1}, n) = n_{2} and (a_{2}, n_{2}) = 1. For every such bijection ϕ choose b ∈ ℕ such that a_{2}b ≡ 1 (mod n_{2}), and let E_{ϕ} be the extension given by

E_{ϕ} :  0 ⟶ ℤ_{n_{1}} ⟶^{a_{1}} ℤ_{n} ⟶^{b} ℤ_{n_{2}} ⟶ 0.

Note that ϕ determines a_{1} uniquely modulo n and b uniquely modulo n_{2}. Thus it determines E_{ϕ} uniquely, and not just uniquely up to isomorphism.

Now suppose in addition that ϕ′ ∈ B_{1} is given by

ϕ′(j_{1}, j_{2}) = ⟨a′_{1}j_{1} + a′_{2}j_{2}⟩_{n}.

Define an equivalence relation ≡ on B_{1} by setting ϕ ≡ ϕ′ if and only if there is an integer r such that (r, n) = 1, a_{1} ≡ ra′_{1} (mod n), and a_{2} ≡ ra′_{2} (mod n_{2}).

Theorem 6.6. The map ϕ ↦ E_{ϕ} gives a one-to-one correspondence between equivalence classes of linear bijections in B_{1} and equivalence classes of extensions of the form

0 ⟶ ℤ_{n_{1}} ⟶ ℤ_{n} ⟶ ℤ_{n_{2}} ⟶ 0.

Proof. Let E be an extension of the form given in the statement of the theorem. By Theorem 6.5 there is an integer c such that 0 ≤ c ≤ d − 1, (c, d) = 1, and E is equivalent to the extension determined by the cocycle f_{c}. Write c = αβ with (α, n_{1}) = (β, n_{2}) = 1. Let a ∈ ℤ_{n_{1}} and b ∈ ℤ_{n_{2}} be integers such that αa ≡ 1 (mod n_{1}) and βb ≡ 1 (mod n_{2}). Then we may assume that E is given by

E :  0 ⟶ ℤ_{n_{1}} ⟶^{n_{2}a} ℤ_{n} ⟶^{b} ℤ_{n_{2}} ⟶ 0.

Set a_{1} = n_{2}a and a_{2} = β, and let ϕ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} be given by

ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1} + a_{2}j_{2}⟩_{n}.

Then ϕ ∈ B_{1}, and E = E_{ϕ}. Thus the map ϕ ↦ E_{ϕ} is surjective on equivalence classes.

Now let ϕ, ϕ′ ∈ B_{1} such that E_{ϕ} ≡ E_{ϕ′}. Assume that ϕ and ϕ′ are given by

ϕ(j_{1}, j_{2}) = ⟨a_{1}j_{1} + a_{2}j_{2}⟩_{n}

and

ϕ′(j_{1}, j_{2}) = ⟨a′_{1}j_{1} + a′_{2}j_{2}⟩_{n}.

Let b, b′ ∈ ℤ_{n_{2}} such that a_{2}b ≡ a′_{2}b′ ≡ 1 (mod n_{2}). Because E_{ϕ} ≡ E_{ϕ′}, there is an integer r and a commutative diagram

E_{ϕ′} :  0 ⟶ ℤ_{n_{1}} ⟶^{a′_{1}} ℤ_{n} ⟶^{b′} ℤ_{n_{2}} ⟶ 0
∥  ↓^{r}  ∥
E_{ϕ} :  0 ⟶ ℤ_{n_{1}} ⟶_{a_{1}} ℤ_{n} ⟶_{b} ℤ_{n_{2}} ⟶ 0.

Then multiplication by r is an automorphism of ℤ_{n}, so (r, n) = 1. Moreover, a_{1} ≡ ra′_{1} (mod n) and rb ≡ b′ (mod n_{2}). It follows that

0 ≡ a_{2}(rb − b′) ≡ ra′_{2}b′ − a_{2}b′ = (ra′_{2} − a_{2})b′ (mod n_{2})

and hence a_{2} ≡ ra′_{2} (mod n_{2}). Thus ϕ ≡ ϕ′, and this completes the proof. □

7. Equivalent Splitting Pairs

In Section 6 we defined a certain equivalence relation ≡ on linear bijections in B_{1}. It seems natural to try to extend this definition to splitting pairs, and the purpose of this section is to study the resulting equivalence relation.

Suppose that ϕ, ϕ′ ∈ B_{1} are given by and

ϕ′(j_{1}, j_{2}) = ⟨a′_{1}j_{1} + a′_{2}j_{2}⟩_{n}.

In the previous section we defined ϕ ≡ ϕ′ if and only if there is an integer r such that (r, n) = 1, a_{1} ≡ ra′_{1} (mod n), and a_{2} ≡ ra′_{2} (mod n_{2}). Similarly, suppose that ψ, ψ′ ∈ B_{2} are given by

ψ(k_{1}, k_{2}) = ⟨b_{1}k_{1} + b_{2}k_{2}⟩_{n}

and

ψ′(k_{1}, k_{2}) = ⟨b′_{1}k_{1} + b′_{2}k_{2}⟩_{n}.

Define an equivalence relation ≡ on B_{2} by setting ψ ≡ ψ′ if and only if there is an integer r such that (r, n) = 1, b_{2} ≡ rb′_{2} (mod n), and b_{1} ≡ rb′_{1} (mod n_{1}).

Finally, suppose that (ϕ, ψ), (ϕ′, ψ′) ∈ B_{1} × B_{2} are splitting pairs. Define an equivalence relation ≡ on B_{1} × B_{2} by setting (ϕ, ψ) ≡ (ϕ′, ψ′) if and only if ϕ ≡ ϕ′ in B_{1} and ψ ≡ ψ′ in B_{2}.

The main result of this section is the next proposition. The proof shows how to construct an equivalent maximal splitting pair from any given pair in B_{1} × B_{2}.

Proposition 7.1. Every splitting pair in B_{1} × B_{2} is equivalent to a maximal splitting pair.

Proof. Let (ϕ, ψ) be a splitting pair in B_{1} × B_{2}. By Lemma 4.1 it follows that ϕ and ψ are given by

ϕ(j_{1}, j_{2}) = ⟨n_{2}a_{1}j_{1} + a_{2}j_{2}⟩_{n}

and

ψ(k_{1}, k_{2}) = ⟨b_{1}k_{1} + n_{1}b_{2}k_{2}⟩_{n}

for some integers a_{1}, a_{2}, b_{1}, b_{2} such that (a_{1}, n_{1}) = (a_{2}, n_{2}) = (b_{1}, n_{1}) = (b_{2}, n_{2}) = 1. Let m_{1} be the largest factor of n_{1} such that (m_{1}, n_{2}) = 1, and let m_{2} be the largest factor of n_{2} such that (m_{2}, n_{1}) = 1. Then there are integers s_{1} and s_{2} such that s_{1}m_{1} ≡ 1 (mod n_{2}) and s_{2}m_{2} ≡ 1 (mod n_{1}). Set a′_{1} = a_{1}, a′_{2} = s_{1}a_{2}, b′_{1} = s_{2}b_{1}, and b′_{2} = b_{2}, and define ϕ′, ψ′ : ℤ_{n_{1}} × ℤ_{n_{2}} → ℤ_{n} by

ϕ′(j_{1}, j_{2}) = ⟨n_{2}a′_{1}j_{1} + m_{1}a′_{2}j_{2}⟩_{n}

and

ψ′(k_{1}, k_{2}) = ⟨m_{2}b′_{1}k_{1} + n_{1}b′_{2}k_{2}⟩_{n}.

Then (ϕ′, ψ′) ∈ B_{1} × B_{2} is a maximal splitting pair. Moreover, n_{2}a′_{1} = n_{2}a_{1} and m_{1}a′_{2} = m_{1}s_{1}a_{2} ≡ a_{2} (mod n_{2}). Hence ϕ ≡ ϕ′ in B_{1}. Similarly, ψ ≡ ψ′ in B_{2}, so (ϕ, ψ) ≡ (ϕ′, ψ′), as desired. □

Proposition 7.2. If (n_{1}, n_{2}) = 1, then all splitting pairs in B_{1} ×B_{2} are equivalent.

Proof. Because (n_{1}, n_{2}) = 1, Theorems 6.5 and 6.6 imply that all elements of B_{1} are equivalent. Similarly, all elements of B_{2} are equivalent, and it follows that B_{1} × B_{2} consists of a single equivalence class. □

Acknowledgements

The authors are grateful to Trudy Weibel for helpful discussions and for bringing their attention to the connection between 2-cocycles and the carry function.

References

1. T. Beth, On the computational complexity of the general discrete Fourier transform, Theoretical Computer Science 51 (1987), 331–339.

2. C. S. Burrus, Index mappings for multidimensional formulation of the DFT and convolution, IEEE Trans. Acoust. Speech Signal Process. 25 (1977), 239–242.

3. M. Clausen, Fast generalized Fourier transforms, Theoretical Computer Science 67 (1989), 55–63.

4. , Fast Fourier transforms for metabelian groups, SIAM J. Computing 18 (3) (1989), 584–593.

5. M. Clausen and U. Baum, Fast Fourier transforms for symmetric groups, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 11, 1993, pp. 27–39.

6. J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301.

7. M. Hegland, On some block algorithms for fast Fourier transforms, Computational techniques and applications: CTAC93 (D. Stewart, H. Gardner, and D. Singleton, eds.), World Scientific, Singapore, pp. 276–284.

8. , A self-sorting in-place fast Fourier transform algorithm suitable for vector and parallel processing, Numer. Math. 68 (1994), 507–547.

9. , Parallel FFTs for real and complex sequences, Tech. report, CMA, Australian National University (1994).

10. , An implementation of multiple and multivariate Fourier transforms on vector processors, SIAM J. Sci. Comput. 16 (1995), 271–288.

11. S. Mac Lane, Homology, Springer–Verlag, New York, 1963.

12. P. N. Swarztrauber, Multiprocessor FFTs, Parallel Comput. 5 (1987), 197–210.

13. C. Van Loan, Computational Frameworks for the Fast Fourier Transform, SIAM, Philadelphia,