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 bandaEditar

Largura de bandaEditar

Formalmente, considere uma matriz  ,  . Se todos os elementos da matriz forem zero fora de uma banda com borda diagonal, cujo intervalo é determinado pelas constantes   e  :

 

então as quantidades   e   são chamadas de largura de banda inferior e largura de banda superior, respectivamente[1] A largura de banda da matriz é o máximo de   e  ; em outras palavras, é o número   tal que   se  .[2]

DefiniçãoEditar

Uma matriz é chamada de matriz banda ou matriz de banda se sua largura de banda for razoavelmente pequena.[necessário esclarecer]

ExemplosEditar

AplicaçõesEditar

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 bandaEditar

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

 

é armazenada como a matriz 6 por 3

 

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:

 

Esta matriz é armazenada como a matriz 6 por 3:

 

Forma de banda de matrizes esparsasEditar

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.[3]

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.[4]

Ver tambémEditar

NotasEditar

ReferênciasEditar

  • 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 externasEditar