Résolution rapide des systèmes de Toeplitz bande par blocs de Toeplitz bandes

RésuméNous présentons une méthode directe pour résoudre un système de Toeplitz bande par blocs de Toeplitz bandes avec une complexité de O(Nlog2N) opérations arithmétiques. L'idée de cet algorithme est de plonger une matrice de Toeplitz bande biniveaux dans une matrice circulante biniveaux. La technique de plonger (resp. de transformer) une matrice de Toeplitz bande dans (resp. à) une matrice de type différente est très connue dans le cas des matrices de Toeplitz scalaires. C'est la première fois qu'on utilise cette technique pour les matrices de Toeplitz bandes biniveaux, ce qui nous permet d'obtenir cette complexité qui est, à notre connaissance, la plus rapide pour résoudre un système de Toeplitz biniveaux bande.

We present a direct method for the solution of N×N block banded Toeplitz systems with banded Toeplitz blocks with computational complexity O(Nlog2N) operations. The idea of this algorithm consists in embedding a two-level banded Toeplitz matrix into a two-level circulant matrix. This technical device is well-known for scalar banded Toeplitz systems, but it never been used for two-level banded Toeplitz systems.