no. 21-22
Analyse numérique
Résolution rapide des systèmes de Toeplitz bande par blocs de Toeplitz bandes

Présenté par : le Comité de rédaction

Houssam, Khalil1 ; Mouhamad, Hossein2 ; Hayssam, Ezzaldine2
1 Institut Camille-Jordan, 43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex, France
2 Laboratoire J.A. Dieudonné, parc Valrose, 06108 Nice cedex 02, France
Comptes Rendus. Mathématique, Tome 348 (2010) no. 21-22, pp. 1221-1224.

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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2010.10.009
Houssam, Khalil 1 ; Mouhamad, Hossein 2 ; Hayssam, Ezzaldine 2

1 Institut Camille-Jordan, 43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex, France
2 Laboratoire J.A. Dieudonné, parc Valrose, 06108 Nice cedex 02, France 
@article{CRMATH_2010__348_21-22_1221_0,
     author = {Houssam, Khalil and Mouhamad, Hossein and Hayssam, Ezzaldine},
     title = {R\'esolution rapide des syst\`emes de {Toeplitz} bande par blocs de {Toeplitz} bandes},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1221--1224},
     publisher = {Elsevier},
     volume = {348},
     number = {21-22},
     year = {2010},
     doi = {10.1016/j.crma.2010.10.009},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2010.10.009/}
}
TY  - JOUR
AU  - Houssam, Khalil
AU  - Mouhamad, Hossein
AU  - Hayssam, Ezzaldine
TI  - Résolution rapide des systèmes de Toeplitz bande par blocs de Toeplitz bandes
JO  - Comptes Rendus. Mathématique
PY  - 2010
SP  - 1221
EP  - 1224
VL  - 348
IS  - 21-22
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2010.10.009/
DO  - 10.1016/j.crma.2010.10.009
LA  - fr
ID  - CRMATH_2010__348_21-22_1221_0
ER  - 
%0 Journal Article
%A Houssam, Khalil
%A Mouhamad, Hossein
%A Hayssam, Ezzaldine
%T Résolution rapide des systèmes de Toeplitz bande par blocs de Toeplitz bandes
%J Comptes Rendus. Mathématique
%D 2010
%P 1221-1224
%V 348
%N 21-22
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2010.10.009/
%R 10.1016/j.crma.2010.10.009
%G fr
%F CRMATH_2010__348_21-22_1221_0
Houssam, Khalil; Mouhamad, Hossein; Hayssam, Ezzaldine. Résolution rapide des systèmes de Toeplitz bande par blocs de Toeplitz bandes. Comptes Rendus. Mathématique, Tome 348 (2010) no. 21-22, pp. 1221-1224. doi : 10.1016/j.crma.2010.10.009. http://www.numdam.org/articles/10.1016/j.crma.2010.10.009/

[1] Bini, Dario; Capovani, Milvio Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra and its Applications, Volume 52–53 (1983), pp. 99-126

[2] Bini, Dario; Capovani, Milvio Tensor rank and border rank of band Toeplitz matrices, SIAM J. Comput., Volume 16 (1987) no. 2, pp. 252-258

[3] Bini, Dario; Pan, Victor Y. Polynomial and Matrix Computations. Vol. 1, Fundamental Algorithms, Progress Theoretical Computer Science, Birkhäuser Boston Inc., Boston, MA, 1994

[4] Bostan, Alin; Jeannerod, Claude-Pierre; Schost, Éric Solving Toeplitz- and Vandermonde-like linear systems with large displacement rank, ISSAC '07: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, ACM, New York, NY, USA, 2007, pp. 33-40

[5] Golub, Gene H.; Van Loan, Charles F. Matrix Computations, The Johns Hopkins University Press, 1996

[6] Jain, A. Fast inversion of banded Toeplitz matrices by circular decompositions, IEEE Transactions on Acoustics, Speech, and Signal Processing, Volume 26 (Apr 1978) no. 1–4, pp. 121-126

[7] Khalil, Houssam Structured and Toeplitz-block-Toeplitz matrices in numeric and symbolic computation http://tel.archives-ouvertes.fr/docs/00/30/69/87/PDF/these.pdf (Ph.D. thesis, Institut Camille Jordan, Université Lyon 1, 2008)

[8] Mourrain, Bernard; Pan, Victor Y. Multivariate polynomials, duality, and structured matrices, Real Computation and Complexity, Schloss Dagstuhl, 1998 (J. Complexity), Volume 16 (2000) no. 1, pp. 110-180

[9] Yunbiao Wang Krishna, H. On fast and superfast algorithms for solving block Toeplitz systems, Twenty-Third Asilomar Conference on Signals, Systems and Computers, Oct. 30–Nov. 1, 1989, pp. 643-647

Cité par Sources :