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.
