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

Khalil Houssam; Hossein Mouhamad; Ezzaldine Hayssam

doi:10.1016/j.crma.2010.10.009

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

Khalil Houssam ¹ ; Hossein Mouhamad ² ; Ezzaldine Hayssam ²

¹ Institut Camille-Jordan, 43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex, France
² Laboratoire J.A. Dieudonné, parc Valrose, 06108 Nice cedex 02, France

Comptes Rendus. Mathématique, Volume 348 (2010) no. 21-22, pp. 1221-1224.

Résumé
Abstract

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 (N \log^{2} N)$ 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 \times N$ block banded Toeplitz systems with banded Toeplitz blocks with computational complexity $O (N \log^{2} N)$ 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 : 2010-08-01
Accepté le : 2010-10-11
Publié le : 2010-10-27

DOI : 10.1016/j.crma.2010.10.009

Affiliations des auteurs :

Khalil Houssam ¹ ; Hossein Mouhamad ² ; Ezzaldine Hayssam ²

¹ Institut Camille-Jordan, 43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex, France
² Laboratoire J.A. Dieudonné, parc Valrose, 06108 Nice cedex 02, France

@article{CRMATH_2010__348_21-22_1221_0,
     author = {Khalil Houssam and Hossein Mouhamad and Ezzaldine Hayssam},
     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},
}

TY  - JOUR
AU  - Khalil Houssam
AU  - Hossein Mouhamad
AU  - Ezzaldine Hayssam
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
DO  - 10.1016/j.crma.2010.10.009
LA  - fr
ID  - CRMATH_2010__348_21-22_1221_0
ER  -

%0 Journal Article
%A Khalil Houssam
%A Hossein Mouhamad
%A Ezzaldine Hayssam
%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
%R 10.1016/j.crma.2010.10.009
%G fr
%F CRMATH_2010__348_21-22_1221_0

Khalil Houssam; Hossein Mouhamad; Ezzaldine Hayssam. Résolution rapide des systèmes de Toeplitz bande par blocs de Toeplitz bandes. Comptes Rendus. Mathématique, Volume 348 (2010) no. 21-22, pp. 1221-1224. doi : 10.1016/j.crma.2010.10.009. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2010.10.009/

Bibliographie
Cité par

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

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

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

[4] Alin Bostan; Claude-Pierre Jeannerod; Éric Schost 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] Gene H. Golub; Charles F. Van Loan Matrix Computations, The Johns Hopkins University Press, 1996

[6] A. Jain 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] Houssam Khalil 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] Bernard Mourrain; Victor Y. Pan Multivariate polynomials, duality, and structured matrices, Real Computation and Complexity, Schloss Dagstuhl, 1998 (J. Complexity), Volume 16 (2000) no. 1, pp. 110-180

[9] H. Yunbiao Wang Krishna 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 :

Commentaires - Politique