Matrice bande

En mathématiques, une matrice bande ou une matrice à bande est une matrice creuse dont les coefficients non nuls sont restreints à une bande diagonale, comprenant la diagonale principale et éventuellement une ou plusieurs diagonales de chaque côté.

Matrice bande

Largeur de bande

Formellement, on considère une matrice carrée n × n A =(ai,j). Si tous les éléments de la matrice sont nuls en dehors d'une bande diagonale dont la plage est déterminée par les constantes k1 et k2 :

a i , j = 0 si j < i − k 1  ou  j > i + k 2 ; k 1 , k 2 ≥ 0. {\displaystyle a_{i,j}=0\quad {\mbox{si}}\quad j<i-k_{1}\quad {\mbox{ ou }}\quad j>i+k_{2};\quad k_{1},k_{2}\geq 0.\,}

alors les quantités k 1 et k 2 sont appelées les largeurs de bande inférieure et largeur de bande supérieure respectivement[1]. La largeur de bande de la matrice est le maximum de k1 et k2 ; autrement dit, c'est le nombre k tel que a i , j = 0 {\displaystyle a_{i,j}=0} si | i − j | > k {\displaystyle |i-j|>k} [2].

Exemples

  • Une matrice bande avec k1 = k2 = 0 est une matrice diagonale
  • Une matrice bande avec k1 = k2 = 1 est une matrice tridiagonale
  • Pour k1 = k2 = 2 on a une matrice pentadiagonale et ainsi de suite.
  • les Matrices triangulaires
    • Pour k1 = 0, k2 = n − 1, on obtient la définition d'une matrice triangulaire supérieure
    • de même, pour k1 = n − 1, k2 = 0 on obtient une matrice triangulaire inférieure.
  • les matrices de Hessenberg supérieure et inférieure
  • les matrices de Toeplitz lorsque la bande passante est limitée.
  • les matrices diagonales par blocs
  • les matrices de déplacement et de cisaillement
  • les matrices sous forme normale de Jordan
  • Une matrice d'horizon, également appelée "matrice de bande variable" — une généralisation de la matrice bande
  • Les inverses des matrices de Lehmer sont des matrices tridiagonales constantes, et sont donc des matrices bandes.

Applications

En analyse numérique, les matrices des problèmes d'éléments finis ou de différences finies sont souvent à bande. Ces matrices peuvent être considérées comme des descriptions du couplage entre les variables du problème ; le fait que la matrice soit une matrice bande correspond au fait que les variables ne sont pas couplées sur des distances arbitrairement grandes. De telles matrices peuvent être encore divisées – par exemple, il existe des matrices en bandes où chaque élément de la bande est différent de zéro. Ceux-ci surviennent souvent lors de la discrétisation de problèmes unidimensionnels.[réf. nécessaire]

Les problèmes dans les dimensions supérieures conduisent également à des matrices bandes, auquel cas la bande elle-même a également tendance à être creuse. Par exemple, une équation aux dérivées partielles sur un domaine carré (utilisant des différences centrales) donnera une matrice avec une largeur de bande égale à la racine carrée de la dimension de la matrice, mais à l'intérieur de la bande, seules 5 diagonales sont non nulles. Malheureusement, l'application du pivot de Gauss (ou de manière équivalente une décomposition LU ou de Cholesky) à une telle matrice entraîne le remplissage de la bande par de nombreux éléments non nuls.

Stockage de bande

Les matrices bandes sont généralement stockées en stockant les diagonales dans la bande ; le reste est implicitement nul.

Par exemple, une matrice tridiagonale a une largeur de bande de 1. La matrice 6 par 6

[ B 11 B 12 0 ⋯ ⋯ 0 B 21 B 22 B 23 ⋱ ⋱ ⋮ 0 B 32 B 33 B 34 ⋱ ⋮ ⋮ ⋱ B 43 B 44 B 45 0 ⋮ ⋱ ⋱ B 54 B 55 B 56 0 ⋯ ⋯ 0 B 65 B 66 ] {\displaystyle {\begin{bmatrix}B_{11}&B_{12}&0&\cdots &\cdots &0\\B_{21}&B_{22}&B_{23}&\ddots &\ddots &\vdots \\0&B_{32}&B_{33}&B_{34}&\ddots &\vdots \\\vdots &\ddots &B_{43}&B_{44}&B_{45}&0\\\vdots &\ddots &\ddots &B_{54}&B_{55}&B_{56}\\0&\cdots &\cdots &0&B_{65}&B_{66}\end{bmatrix}}}

est stockée dans un matrice 6 par 3

[ 0 B 11 B 12 B 21 B 22 B 23 B 32 B 33 B 34 B 43 B 44 B 45 B 54 B 55 B 56 B 65 B 66 0 ] . {\displaystyle {\begin{bmatrix}0&B_{11}&B_{12}\\B_{21}&B_{22}&B_{23}\\B_{32}&B_{33}&B_{34}\\B_{43}&B_{44}&B_{45}\\B_{54}&B_{55}&B_{56}\\B_{65}&B_{66}&0\end{bmatrix}}.}

Une économie supplémentaire est possible lorsque la matrice est symétrique. Par exemple, on considère une matrice symétrique 6 par 6 avec une bande passante supérieure de 2 :

[ A 11 A 12 A 13 0 ⋯ 0 A 22 A 23 A 24 ⋱ ⋮ A 33 A 34 A 35 0 A 44 A 45 A 46 s y m A 55 A 56 A 66 ] . {\displaystyle {\begin{bmatrix}A_{11}&A_{12}&A_{13}&0&\cdots &0\\&A_{22}&A_{23}&A_{24}&\ddots &\vdots \\&&A_{33}&A_{34}&A_{35}&0\\&&&A_{44}&A_{45}&A_{46}\\&\mathrm {sym} &&&A_{55}&A_{56}\\&&&&&A_{66}\end{bmatrix}}.}

Cette matrice est stockée en tant que matrice 6 par 3 :

[ A 11 A 12 A 13 A 22 A 23 A 24 A 33 A 34 A 35 A 44 A 45 A 46 A 55 A 56 0 A 66 0 0 ] . {\displaystyle {\begin{bmatrix}A_{11}&A_{12}&A_{13}\\A_{22}&A_{23}&A_{24}\\A_{33}&A_{34}&A_{35}\\A_{44}&A_{45}&A_{46}\\A_{55}&A_{56}&0\\A_{66}&0&0\end{bmatrix}}.}

Forme bandée des matrices creuses

D'un point de vue informatique, travailler avec des matrices bandes est toujours préférable à travailler avec des matrices carrées de même dimension. Une matrice bande peut être assimilée en complexité à une matrice rectangulaire dont le nombre de lignes est égale à la largeur de bande de la matrice bande. Ainsi, le travail nécessaire pour effectuer des opérations telles que la multiplication diminue considérablement, ce qui entraîne souvent d'énormes économies en termes de temps de calcul et de complexité.

Comme les matrices creuses se prêtent à un calcul plus efficace que les matrices denses, ainsi qu'à une utilisation plus efficace du stockage informatique, de nombreuses recherches se sont concentrées sur la recherche de moyens de minimiser la largeur de la bande (ou de minimiser directement le remplissage) en appliquant des permutations à la matrice, ou à d'autres transformations d'équivalence ou de similarité[3].

L'algorithme de Cuthill-McKee peut être utilisé pour réduire la largeur de bande d'une matrice symétrique creuse. Il existe cependant des matrices pour lesquelles l'algorithme inverse de Cuthill-McKee fonctionne mieux. De nombreuses autres méthodes sont utilisées.

Le problème de trouver une représentation d'une matrice avec une bande minimale au moyen de permutations de lignes et de colonnes est NP-difficile [4].

Articles connexes

Notes

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Band matrix » (voir la liste des auteurs).

Références

  • (en) Kendall E. Atkinson, An Introduction to Numerical Analysis, John Wiley & Sons, (ISBN 0-471-62489-6).
  • (en) Timothy A. Davis, Direct Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, (ISBN 978-0-898716-13-9).
  • (en) Uriel Feige, Algorithm Theory - SWAT 2000, vol. 1851, coll. « Lecture Notes in Computer Science », (DOI 10.1007/3-540-44985-X_2).
  • (en) Gene H. Golub et Charles F. Van Loan, Matrix Computations, Baltimore, Johns Hopkins, (ISBN 978-0-8018-5414-9).
  • (en) WH Press, SA Teukolsky, WT Vetterling et BP Flannery, Numerical Recipes: The Art of Scientific Computing, New York, Cambridge University Press, (ISBN 978-0-521-88068-8, lire en ligne), « Section 2.4 ».

Liens externes

  • Informations relatives à LAPACK et aux matrices de bandes
  • Un tutoriel sur les matrices en bandes et autres formats de matrices creuses
  • icône décorative Portail de l’algèbre