Fast Fourier Methods in Computational Complex Analysis
Peter Henrici · SIAM Review · 1979
In this paper we discuss the discrete Fourier transform and point out some computational problems in (mainly) complex analysis where it can be fruitfully applied. We begin by describing the elementary properties of the transform and its efficient implementation, both in the one-dimensional and in the multi-dimensional case, by the reduction formulas of Cooley, Lewis, and Welch (IBM Res, paper, 1967).The following applications are then discussed: Calculation of Fourier coefficients using attenuation factors; solution of Symm’s integral equation in numerical conformal mapping; trigonometric interpolation; determination of conjugate periodic functions and their application to Theodorsen’s integral equation for the conformal mapping of simply and of doubly connected regions; determination of Laurent coefficients with applications to numerical differentiation, generating functions, and the numerical inversion of Laplace transforms; determination of the “density” of the zeros of high degree polynomials. We then discuss convolution and its application to time series analysis, to the multiplication of polynomials and of large integers, and to fast Poisson solvers. The paper concludes with an account of some recent results of Brent and Kung (Carnegie-Mellon Univ., 1975, 1976) concerning fast algorithms for manipulating power series