Matriz de bandas

En matemáticas , particularmente en teoría de matrices , una matriz de banda o matriz de banda es una matriz dispersa cuyos elementos no nulos están confinados a una banda diagonal , que comprende la diagonal principal y cero o más diagonales a cada lado.

• Una matriz de banda con k ₁ = k ₂ = 0 es una matriz diagonal , con ancho de banda 0.
• Una matriz de banda con k ₁ = k ₂ = 1 es una matriz tridiagonal , con ancho de banda 1.
• Para k ₁ = k ₂ = 2 se tiene una matriz pentadiagonal y así sucesivamente.
• Matrices triangulares
  • Para k ₁ = 0, k ₂ = n − 1, se obtiene la definición de una matriz triangular superior.
  • De manera similar, para k ₁ = n − 1, k ₂ = 0 se obtiene una matriz triangular inferior.
• Matrices de Hessenberg superior e inferior
• Matrices de Toeplitz cuando el ancho de banda es limitado.
• Matrices diagonales por bloques
• Matrices de desplazamiento y matrices de cizallamiento
• Matrices en forma normal de Jordan
• Una matriz de horizonte , también llamada "matriz de banda variable" , es una generalización de la matriz de banda. 
• Las inversas de las matrices de Lehmer son matrices tridiagonales constantes y, por lo tanto, son matrices de banda.

En análisis numérico , las matrices de problemas de elementos finitos o diferencias finitas suelen ser de tipo banda. Estas matrices pueden interpretarse como descripciones del acoplamiento entre las variables del problema; la propiedad de banda se debe a que las variables no están acopladas a distancias arbitrariamente grandes. Dichas matrices pueden subdividirse aún más ; por ejemplo, existen matrices de banda donde cada elemento de la banda es distinto de cero. 

Los problemas en dimensiones superiores también dan lugar a matrices con banda, en cuyo caso la banda misma tiende a ser dispersa. Por ejemplo, una ecuación diferencial parcial en un dominio cuadrado (utilizando diferencias centrales) produce una matriz con un ancho de banda igual a la raíz cuadrada de la dimensión de la matriz, pero dentro de la banda solo 5 diagonales son distintas de cero. Desafortunadamente, al aplicar la eliminación gaussiana (o, equivalentemente, una descomposición LU ) a dicha matriz, la banda se llena con muchos elementos distintos de cero.

Las matrices de banda generalmente se almacenan guardando las diagonales en la banda; el resto es implícitamente cero.

Por ejemplo, una matriz tridiagonal tiene un ancho de banda de 1. La matriz de 6 por 6

${\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}}}$

se almacena como una matriz de 6 por 3

${\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}}.}$

Es posible obtener un ahorro adicional cuando la matriz es simétrica. Por ejemplo, consideremos una matriz simétrica de 6x6 con un ancho de banda superior de 2:

${\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}\\&sym&&&A_{55}&A_{56}\\&&&&&A_{66}\end{bmatrix}}.}$

Esta matriz se almacena como una matriz de 6x3:

${\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}}.}$

Desde el punto de vista computacional, trabajar con matrices de banda siempre es preferible a trabajar con matrices cuadradas de dimensiones similares . Una matriz de banda puede compararse en complejidad con una matriz rectangular cuya dimensión de fila es igual al ancho de banda de la matriz de banda. Por lo tanto, el trabajo que implica realizar operaciones como la multiplicación se reduce significativamente, lo que a menudo conlleva un gran ahorro en términos de tiempo y complejidad de cálculo .

Dado que las matrices dispersas se prestan a un cálculo más eficiente que las matrices densas, así como a una utilización más eficiente del almacenamiento informático, se ha investigado mucho sobre cómo minimizar el ancho de banda (o minimizar directamente el relleno) aplicando permutaciones a la matriz u otras transformaciones de equivalencia o similitud similares. ^{[ 3 ]}

El algoritmo de Cuthill-McKee puede utilizarse para reducir el ancho de banda de una matriz simétrica dispersa . Sin embargo, existen matrices para las que el algoritmo inverso de Cuthill-McKee ofrece mejores resultados. Existen muchos otros métodos en uso.

El problema de encontrar una representación de una matriz con ancho de banda mínimo mediante permutaciones de filas y columnas es NP-difícil . ^{[ 4 ]}

• Matriz diagonal
• Ancho de banda del gráfico
• Matriz aleatoria

• Atkinson, Kendall E. (1989), Introducción al análisis numérico , John Wiley & Sons, ISBN 0-471-62489-6.
• Davis, Timothy A. (2006), Métodos directos para sistemas lineales dispersos , Sociedad de Matemáticas Industriales y Aplicadas, ISBN 978-0-898716-13-9.
• Feige, Uriel (2000), "Cómo afrontar la NP-dificultad del problema del ancho de banda de grafos", Algorithm Theory - SWAT 2000 , Lecture Notes in Computer Science, vol.  1851, pp. 129–145 , doi : 10.1007/3-540-44985-X_2 .
• Golub, Gene H .; Van Loan, Charles F. (1996), Matrix Computations (3.ª  ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.4" , Numerical Recipes: The Art of Scientific Computing (3.ª  ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8Archivado del original el 4 de marzo de 2016 , consultado el 8 de agosto de 2011..

• Información relativa a LAPACK y matrices de bandas
• Un tutorial sobre matrices de banda y otros formatos de matrices dispersas.