A Split Fast Fourier Transform Algorithm for Block Toeplitz Matrix-Vector Multiplication

La modélisation des phénomènes physiques invariants par translation, dans une base vectorielle spatiale, entraine des systèmes d’équations qui peuvent être représentés par des matrices de Toeplitz par bloc multi-niveaux. C’est notamment le cas des phénomènes liés à l’électromagnétisme ou l’acoustique. La résolution d’équations impliquant ces matrices requiert généralement une méthode de résolution itérative, nécessitant un grand nombre de multiplications de matrice de Toeplitz par bloc avec des vecteurs. Ainsi, pour simuler des problèmes physiques de grande taille, il est indispensable d’améliorer l’efficacité de ces opérations. Il existe un grand nombre de méthodes réalisant ces multiplications, mais chacune présente des limites majeures. Les plus prometteuses de ces méthodes sont celle par insertion de matrices circulantes et celle par décomposition tensorielle en paquet. Malheureusement, ces méthodes présentent des temps de calculs et des besoins en mémoire qui augmentent rapidement avec la taille du système ou le rang du tenseur. Dans le cas de vecteurs sources quelconques, le calcul de la décomposition tensorielle est plus coûteux que la multiplication directe. Aussi, lorsque l’on étend l’insertion de matrices circulantes aux matrices de Toeplitz par bloc en d dimensions, l’insertion entraine l’introduction d’un grand nombre de coefficients redondants. Dans ce cas, seul une proportion de 1/2d du vecteur traité dans le calcul contient des informations utiles. Cette redondance conduit rapidement à une surcharge de mémoire et à une complexité opérationnelle élevée. L’algorithme présenté dans ce mémoire a pour objectif de répondre à ce problème d’inefficacité en reportant au plus tard les insertions et en avançant au plus tôt les projections. Cette stratégie permet de calculer les transformées de Fourier sur un nombre réduit de coefficients, diminuant ainsi la complexité par un facteur de d/ 2 − 2−d+1 et la demande en mémoire maximale de 2/ (d + 1)2−d+1. Pour une multiplication matrice-vecteur en trois dimensions, le ratio entre la complexité théorique de la méthode standard par insertion de matrices circulantes et celle de la version améliorée de cette méthode tend vers 12/7 lorsque la taille de la matrice de Toeplitz par bloc tend vers l’infini pour chaque niveau. De plus, l’algorithme utilise une propriété de la transformée de Fourier rapide afin de séparer le vecteur transformé en deux vecteurs de coefficients d’indices paires et impaires respectivement, et ce pour chaque transformée de Fourier. Cela résulte en une structure arborescente des tâches de l’algorithme.