Algebraic and Combinatorial Circuits - Models of Computation: Exploring the Power of Computing - page 265

Then f r ,the r th component of F n ( a ) ,isdefinedas

n− 1

f r = p ( ω r )= a k ω rk

(6.22)

k = 0

This computation is equivalent to the following matrix-vector multiplication:

F n ( a )=[ w ij ] × a

(6.23)

where [ ω ij ] is the n

n Vandermonde matrix whose i , j entry is ω ij ,0 × ≤ i , j ≤ n −

1, and

a is treated as a column vector.
The n -point inverse discrete Fourier transform F − 1

: R n R n

→

is defined as the values

n

of the following polynomial q ( x ) at the inverse n th roots of unity:

q ( x )=( f 0 + f 1 x + f 2 x 2 + + f n− 1 x n− 1 ) /n

···

(6.24)

That is, the inverse DFT maps an n -tuple f to an n -tuple g ,namely, F − n ( f )= g ,where g s
is defined as follows:

n− 1

g s = q ( ω −s )= 1
n

f l ω −ls (6.25)

l = 0

This computation is equivalent to the following matrix-vector multiplication:
F − n ( f )= 1

n ω −ij

× f

Because of the following lemma it is legitimate to call F − 1 the inverse of F n .

n

LEMMA 6.7.3 For all a ∈ R n , a = F − n ( F n ( a )) .
Proof Let f = F n ( a ) and g = F − n ( f ) .Then g s satisfies the following:

n − n − n −

1 1 1

g s = 1
n

f l ω −ls = 1
n

a k ω ( k−s ) l

l = 0 l = 0 k = 0

n − n −

1 1

1
n

ω ( k−s ) l = a k

k = 0 l = 0

= a s

The second equation results from a change in the order of summation. The last follows
from the definition of n th roots of unity. It follows that the matrix [ ω −ij /n ] is the inverse
of [ ω ij ] .

The computation of the n -point DFT and its inverse using the naive algorithms suggested
by their definitions requires O ( n 2 ) steps. Below we show that a fast DFT algorithm exists for
which only O ( n log n ) steps suffice.