When the nodes 
are equidistant on the unit circle and all weights
are unity, then interpolation and least-squares approximation of
a given function
by algebraic or trigonometric polynomials can be carried out rapidly by the
FFT algorithm. This section describes in some detail how our downdating scheme
may be
combined with the FFT algorithm to achieve rapid schemes for
interpolation when the nodes are essentially equidistant. More precisely,
we will consider the case when the set of nodes 
in the
inner product (1.1) is a subset of the set of
equidistant nodes 
, where
is a small positive integer. In our operation count we will
assume that 
is independent of m. The weights
in (1.1) are all assumed to be unity.
Let f
denote a complex-valued function, whose values 
, 
,
are explicitly known. We remark that a
representation of the interpolating polynomial
in Newton form can be computed in
arithmetic operations. The Vandermonde solver by
Björck and Pereyra [2] can be used to determine a
representation of 
in terms of the
monomial basis, and requires also 
arithmetic operations. Our
scheme only requires 
arithmetic operations and yields a
representation of 
in the basis of Szego polynomials.
Let 
denote the complement of the set
in
,
and let 
, 
.
Thus,
f is defined at the N roots of unity 
,
and we can compute the Fourier coefficients of the
polynomial 
that
interpolates f at these nodes by the FFT algorithm in
arithmetic operations.
Using the Schur parameters given in Example 1.1, we
apply
Algorithm 2.1
times to eliminate the nodes 
, 
,
from the inner product.
This requires 
arithmetic operations and yields the Fourier
coefficients of the desired interpolating
polynomial 
. The Fourier coefficients of the least-squares
approximants
with n<m are, of course, a subset of the
Fourier
coefficients of 
.
A scheme closely related to the one outlined above can be used to compute
trigonometric polynomials rapidly. Let 
and 
be the nodes introduced above,
and define 
, 
,
and 
, 
.
Also assume that m = 2r+1.
Let 
be a real-valued function defined at the nodes 
and let 
, 
.
We wish to compute a trigonometric polynomial
that minimizes the sum
This can be accomplished as follows. First solve the minimization problem
by the FFT algorithm in 
arithmetic operations, and denote
the optimal coefficients by 
.
Remove the nodes 
, 
, by applying the
downdating scheme 
times to the polynomial
, where
.
This requires 
arithmetic operations and yields
the polynomial 
.
The desired trigonometric polynomial is then given by
, 
.