Un algorithme pour le calcul machine de séries de Fourier complexes

Une méthode efficace pour le calcul des interactions d'une expérience factorielle de 2m a été introduite par Yates et est largement connue sous son nom. La généralisation à 3m a été donnée par Box et al. 1. Good 2 a généralisé ces méthodes et a proposé des algorithmes élégants dont une classe d'applications est le calcul des séries de Fourier. Dans leur pleine généralité, les méthodes de Good s'appliquent à certains problèmes dans lesquels il faut multiplier un vecteur N-J par une matrice N X N qui peut être facteurisée en m matrices éparses, où m est proportionnel à log N. Cela aboutit à une procédure nécessitant un nombre d'opérations proportionnel à N log N plutôt qu'à N². Ces méthodes sont appliquées ici au calcul de séries de Fourier complexes. Elles sont utiles dans des situations où le nombre de points de données est, ou peut être choisi pour être, un nombre hautement composite. L'algorithme est ici dérivé et présenté sous une forme plutôt différente. Une attention particulière est accordée au choix de N. Il est également montré comment un avantage spécial peut être obtenu dans l'utilisation d'un ordinateur binaire avec N = 2m et comment tout le calcul peut être effectué dans le tableau des emplacements de stockage de données N utilisés pour les coefficients de Fourier donnés. Considérons le problème de calcul de la série de Fourier complexe.