We now present the results of some numerical experiments with our downdating procedure. These experiments were performed in FORTRAN on a SparcStation SLC at Northern Illinois University, on which there are approximately 7 and 16 significant decimal digits in single-precision and double-precision calculations, respectively.

The first set of experiments compares the accuracy of the
downdating procedure with that of the updating procedure IUQR described
in [10].
We input **N** unimodular nodes ,
**N** positive weights , and **N** complex function values
. For any positive integer ,
let denote the
vector of Fourier coefficients of the solution of
(1.6) with **n=m**, and let
denote the vector of Schur parameters determined by
(1.1).

We first obtain computed vectors and using an
implementation of the IUQR algorithm in single-precision arithmetic.
We then repeatedly apply
a single-precision implementation of Algorithm 2.1
to compute and for decreasing values of
**m**. The application of Algorithm 2.1 removes the node
from the inner product to compute the solution of (1.6)
with **n=m=N-k**.
After each downdating step, we calculate the
relative error in ,
,
and the error in , ,
where denotes the Euclidean norm of .
We also solve each problem of order **m**
using the IUQR algorithm in single-precision arithmetic and compute
the resulting errors.
The results of the IUQR algorithm in double-precision arithmetic
as used as exact answers in the error calculations.
The following tables display the resulting errors for the downdating
procedure (DD) and the updating procedure (UD).
In each of the following experiments, each function
value has its real part and imaginary part randomly generated
according to a uniform distribution in .

We first choose the nodes to be the roots of unity
, and uniform
weights. Table 1 shows the errors for problems of order
**m = N-k** for various values of **k**. Table 1 also shows the
results with the same choice of nodes and weights, except that the
nodes are permuted in a random way. This permutation
changes the nodes that are
deleted as well as the order in which the nodes are added in the
updating procedure.
It should be noted that the errors
in the downdating procedure can be expected to increase as **k**
increases.
Table 2 shows that similar results are obtained with the same
set of nodes and randomly generated weights in .

Table 3 shows the results obtained
with uniform weights and the **N** nodes
in , both in their original order and in a random order.
Here again, the downdating procedure seems to be performing well.

Table 4 shows the results when the initial **300** nodes
are randomly selected points on the unit circle. In this example,
the error in the downdating procedure displays a sudden increase
at **k=10**. In this step the error in the computed downdated weight,
, was greater than .
Observe that the error incurred at this downdating step propagated to the
subsequent downdating steps, but the errors seem to grow gradually.
Other experiments with random nodes produced similar results.
It should be noted that in our experiments, a large
error in the computed weight did not always coincide with
a large jump in the errors.
It is clear that more work needs to be done in order
to understand the numerical aspects of the updating and downdating
problems.

Our final experiment tests the accuracy and speed
of the procedure described in Section 3 for downdating the FFT.
The **N**-point FFT is used to obtain the Fourier coefficients of
the interpolating polynomial . A randomly selected set of
nodes is then removed from the inner product using Algorithm 2.1.
This experiment was run with **N=1024** and **N=2048**.
Table 5 shows the
computed error after **k** downdating steps for various values of **k**.
As above, we use the results of the IUQR
algorithm in double precision arithmetic as exact answers for error
checking.
We also display the amount of CPU time required by the
FFT with **k** downdating steps and the time required by the
single-precision IUQR algorithm on the problem of order **m=N-k**.
It is interesting to note that the downdating procedure produces
substantially more accurate answers faster than the IUQR algorithm
even for moderately sized values of **k**.

**Table 1:** **300** nodes with equispaced arguments in ; uniform
weights.

**Table 2:** **300** nodes with equispaced arguments in ;
random weights in

**Table 3:** **300** nodes with equispaced arguments in ;
uniform weights.

**Table 4:** **300** nodes with random arguments in ;
uniform weights.

Tue Feb 14 12:51:53 CST 1995