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 . 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.
Table 5: Downdating the FFT