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é.
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 :
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 si [2].
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.
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
est stockée dans un matrice 6 par 3
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 :
Cette matrice est stockée en tant que matrice 6 par 3 :
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].