Fast Algorithm for the Evaluation of Trigonometric Series

摘要

Fourier techniques have been a popular analytical tool in the study of physicsand engineering for more than two centuries. A reason for the usefulness of such techniques is that certain trigonometric functions are eigenfunctions of the differentiation operator and can be effectively used to model solutions of differential equations which arise in the fields mentioned above. With the arrival of digital computers, it became theoretically possible to calculate the Fourier series and Fourier transform of a function numerically. This was unrealistic in practice however owing to the prohibitive complexity of even modesty sized problems. A major break-through in overcoming this difficulty was the development of the Fast Fourier Transform (FFT) algorithm in the 1960s which established Fourier analysis as a useful and practical numerical tool. This paper presents an algorithm for the rapid evaluation of expressions of a certain form.