Une mesure de la distance par rapport à la diagonale principale où les entrées non nulles significatives d'un opérateur linéaire discrétisé (matrice) sont concentrées, généralement quantifiée par la distance maximale |i-j| pour laquelle la matrice A(i,j) est non nulle (ou la demi-largeur de bande en convention symétrique).

Principe

Le graphe et l'ordonnancement des degrés de liberté déterminent la largeur de bande : des stencils locaux ou une connectivité d'éléments limitée produisent une faible largeur de bande, laquelle contrôle le format de stockage, le remplissage lors de la factorisation et la complexité de certains solveurs directs.

Démonstration

Une discrétisation différenciée finie unidimensionnelle du second ordre avec couplage aux voisins immédiats donne une matrice tridiagonale avec largeur de bande 1 (demi-largeur de bande égale à 1), tandis qu'un ordonnancement naïf d'un maillage multidimensionnel peut augmenter la largeur de bande et donc le coût de la factorisation LU.

Mauvaise application

Utiliser la largeur de bande comme seul prédicteur de coût de solveur sans tenir compte de l'irrégularité du motif de sparsité, du remplissage provoqué par la factorisation, ou de l'effet du réordonnancement et de la structure par blocs ; ou optimiser la largeur de bande au détriment des schémas de communication parallèles.

Conséquence

Une faible largeur de bande permet un stockage en bandes compact, des solveurs directs en bandes efficaces et un remplissage réduit ; reconnaître et réduire la largeur de bande par réordonnancement (par ex. Cuthill–McKee inversé) peut abaisser fortement le coût de factorisation pour certains problèmes.

Inversion

Largeur complète ou couplage global où des entrées significatives existent loin de la diagonale, entraînant une grande largeur de bande et nécessitant des techniques de stockage dense ou une factorisation avec un remplissage important.

Limite

Se réfère spécifiquement à la distance géométrique à la diagonale dans l'espace d'indices matriciels et exclut d'autres notions appelées 'bande passante' (bande de signaux, bande passante de communication) sauf si le contexte est la discrétisation en algèbre linéaire.

Tension sémantique

La largeur de bande entre en tension avec des métriques de sparsité plus fines (profil, enveloppe, tailles de séparateurs de graphe) : c'est un résumé scalaire simple qui peut masquer des caractéristiques de motif critiques pour le coût algorithmique.

Synthèse

La largeur de bande est la mesure de distance à la diagonale de concentration des non-nuls dans un opérateur linéaire discret ; elle oriente les choix de stockage et de solveur et peut être réduite par réordonnancement, mais doit être évaluée conjointement avec la structure complète de sparsité pour prévoir les performances.