Matriz banda

Em matemática, particularmente na teoria matricial, uma matriz banda é uma matriz esparsa cujas entradas diferentes de zero estão confinadas a uma banda diagonal, compreendendo a diagonal principal e zero ou mais diagonais em cada lado.

Matriz banda

Largura de banda

Formalmente, considere uma matriz $n\mathrm {x} n$, $A=(a_{i,j})$. Se todos os elementos da matriz forem zero fora de uma banda com borda diagonal, cujo intervalo é determinado pelas constantes $k_{1}$ e $k_{2}$:

$a_{i,j}=0\quad {\mbox{se}}\quad j<i-k_{1}\quad {\mbox{ ou }}\quad j>i+k_{2};\quad k_{1},k_{2}\geq 0.\,$

então as quantidades $k_{1}$ e $k_{2}$ são chamadas de largura de banda inferior e largura de banda superior, respectivamente A largura de banda da matriz é o máximo de $k_{1}$ e $k_{2}$; em outras palavras, é o número $k$ tal que $a_{i,j}=0$ se $|i-j|>k$.

Definição

Uma matriz é chamada de matriz banda ou matriz de banda se sua largura de banda for razoavelmente pequena.

Exemplos

• Uma matriz banda com $k_{1}=k_{2}=0$ é uma matriz diagonal
• Uma matriz banda com $k_{1}=k_{2}=1$ é uma matriz tridiagonal
• Para $k_{1}=k_{2}=2$, temos uma matriz pentadiagonal e assim por diante.
• Matrizes triangulares
  • Para $k_{1}=0$, $k_{2}=n-1$, obtém-se a definição de uma matriz triangular superior
  • da mesma forma, para $k_{1}=n-1$, $k_{2}=0$ obtém-se uma matriz triangular inferior.
• Matrizes de Hessenberg superior e inferior
• Matrizes de Toeplitz quando a largura de banda é limitada.
• Matrizes diagonais de bloco
• Matrizes de deslocamento e matrizes de cisalhamento
• Matrizes na forma canônica de Jordan
• Uma matriz de horizonte, também chamada de "matriz banda variável" – uma generalização da matriz banda
• As inversas das matrizes de Lehmer são matrizes tridiagonais constantes e, portanto, matrizes banda.

Aplicações

Na análise numérica, matrizes de problemas de elementos finitos ou diferenças finitas são frequentemente agrupadas. Essas matrizes podem ser vistas como descrições do acoplamento entre as variáveis do problema; a propriedade com bandas corresponde ao fato de que as variáveis não são acopladas em distâncias arbitrariamente grandes. Essas matrizes podem ser divididas posteriormente – por exemplo, matrizes banda existem onde cada elemento na banda é diferente de zero. Muitas vezes surgem ao discriminar problemas unidimensionais.^{[carece de fontes]}

Problemas em dimensões superiores também levam a matrizes banda, caso em que a própria banda tende a ser esparsa. Por exemplo, uma equação diferencial parcial em um domínio quadrado (usando diferenças centrais) produzirá uma matriz com largura de banda igual à raiz quadrada da dimensão da matriz, mas dentro da banda apenas 5 diagonais são diferentes de zero. Infelizmente, a aplicação de eliminação Gaussiana (ou equivalentemente uma decomposição LU) a tal matriz resulta na banda sendo preenchida por muitos elementos diferentes de zero.

Armazenamento de banda

Matrizes banda são geralmente armazenadas armazenando as diagonais na banda; o resto é implicitamente zero.

Por exemplo, uma matriz tridiagonal tem largura de banda 1. A matriz 6 por 6

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

é armazenada como a matriz 6 por 3

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

Uma economia adicional é possível quando a matriz é simétrica. Por exemplo, considere uma matriz simétrica 6 por 6 com uma largura de banda superior de 2:

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

Esta matriz é armazenada como a matriz 6 por 3:

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

Forma de banda de matrizes esparsas

Do ponto de vista computacional, trabalhar com matrizes banda é sempre preferencial a trabalhar com matrizes quadradas de dimensões semelhantes. Uma matriz banda pode ser comparada em complexidade a uma matriz retangular cuja dimensão da linha é igual à largura de banda da matriz de banda. Assim, o trabalho envolvido na execução de operações como a multiplicação cai significativamente, muitas vezes levando a uma enorme economia em termos de tempo de cálculo e complexidade.

Como matrizes esparsas se prestam a cálculos mais eficientes do que matrizes densas, bem como na utilização mais eficiente de armazenamento de computador, tem havido muitas pesquisas focadas em encontrar maneiras de minimizar a largura de banda (ou minimizar diretamente o preenchimento) aplicando permutações para a matriz, ou outras transformações de equivalência ou similaridade.

O algoritmo Cuthill–McKee pode ser usado para reduzir a largura de banda de uma matriz simétrica esparsa. Existem, no entanto, matrizes para as quais o algoritmo reverso de Cuthill–McKee tem melhor desempenho. Existem muitos outros métodos em uso.

O problema de encontrar uma representação de uma matriz com largura de banda mínima por meio de permutações de linhas e colunas é NP-difícil.

Ver também

• Largura de banda de grafos

Referências

• Atkinson, Kendall E. (1989), An Introduction to Numerical Analysis, ISBN 0-471-62489-6, John Wiley & Sons .
• Davis, Timothy A. (2006), Direct Methods for Sparse Linear Systems, ISBN 978-0-898716-13-9, Society for Industrial and Applied Mathematics .
• Feige, Uriel (2000), «Coping with the NP-Hardness of the Graph Bandwidth Problem», Algorithm Theory - SWAT 2000, Lecture Notes in Computer Science, 1851, pp. 129–145, doi:10.1007/3-540-44985-X_2  .
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations, ISBN 978-0-8018-5414-9 3rd ed. , Baltimore: Johns Hopkins .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 2.4», Numerical Recipes: The Art of Scientific Computing, ISBN 978-0-521-88068-8 3rd ed. , New York: Cambridge University Press .

Ligações externas

• Information pertaining to LAPACK and band matrices
• A tutorial on banded matrices and other sparse matrix formats