next up previous
Next: Computed examples Up: Downdating of Szego Previous: Downdating of Szego

Downdating and the FFT algorithm

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



next up previous
Next: Computed examples Up: Downdating of Szego Previous: Downdating of Szego



Greg Ammar
Tue Feb 14 12:51:53 CST 1995