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 , .

Tue Feb 14 12:51:53 CST 1995