Fast parallel algorithms for computing trigonometric sums

In this paper we present new parallel versions of sequential Goertzel and Reinsch algorithms for calculating trigonometric sums. The new algorithms use a recently introduced, very efficient BLAS-based algorithm for solving linear recurrence systems with constant coefficients. To achieve their portability across different shared-memory parallel architectures, the algorithms have been implemented in Fortran 77 and OpenMP We also present experimental results performed on a two processor Pentium III computer running under Linux operating system with Atlas as an efficient implementation of BLAS. The new algorithms are up to 60-90% faster than the equivalent sequential Goertzel and Reinsch algorithms, even on one processor.

1. Introduction

Let us consider the problem of computing trigonometric sums

$$C(x)=\sum\limits_{k=0}^{n}b_{k}\cos kx \ {\rm and}\ S(x)=\sum\limits_{k=1}^{n}b_{k}\sin kx, \eqno{\hbox{(1)}}$$ which is very important for some numerical algorithms which arise in scientific computing [5], [10], [14], [21]-. For ex-ample, in trigonometric interpolation the sums (1) are used for computing values of trigonometric polynomials $$p(x)=\beta_{0}+\beta_{1}e^{ix}+\ldots+\beta_{N-1}e^{(N-1)ix}. \eqno{\hbox{(2)}}$$