Matrizes estruturadas (da apostila de W. Honda e I. Paraboni

   O objetivo deste post é esclarecer idéias que fazem matrizes esparsas (no caso estruturadas) tão importantes.
   A álgebra de matrizes (ou álgebra linear...) é aplicada para modelar ou para simular os mais variados processos dentre eles: processos químicos (sistemas de reações químicas que resultam em um ou mais produtos de grande valor), mecânica de fluidos (consequentemente previsão do tempo - com impacto na agricultura), circuitos elétricos (desde distribuição de energia até projeto e simulação de circuitos integrados), processamento de imagens (imagens médicas, realidade virtual, jogos,...).
    Nestes processos milhares ou até milhões de sistemas lineares com milhares de variáveis precisam ser resolvidos. É algo que um computador faz, mas precisa de muita memória e capacidade de processamento, OU de algoritmos que aproveitam a estrutura do problema (das matrizes) para economizar memória e processamento.
    Em problemas muito grandes é até comum que as matrizes que os representam tenham muitos elementos nulos (da ordem de 90% da matriz) que poderiam não ser representados e com isso não ocupar memória.
    Deve-se considerar também a ordem e frequência com que os elementos da matriz serão visitados. Por exemplo em um produto de matrizes: A x B, A os elementos de A serão varridos por linhas e os de B por colunas, em ordem. Ligar os elementos não nulos nas linhas e nas colunas (listas ligadas) pode ser uma boa estratégia para poupar memória e operações. Algo similar ocorre na fatoração LU (triangularização de matrizes) e na fatoração QR - estas duas usadas para resolver sistemas lineares.
    Na fatoração LU, as matriz M é fatorada em duas: L - triangular inferior e U - triangular superior. Em geral as duas são armazenadas juntas (é o que faz o algoritmo de Gauss), mas apenas U é necessária para resolver o sistema. Neste caso seria vantajoso armazenar apenas U. Existe uma forma de armazenar e indexar matrizes triangulares.
   Da mesma forma, existem formas de armazenar matrizes diagonais e matrizes tridiagonais.


Matriz diagonal
(a) tamanho do vetor de alocação: n
(b) elementos não nulos m(i,j) são tais que i == j;
(c) endereçamento: m(i,j) == V(i) ou j...

Em código:

double *criaMatrizDiagonal (int n) {
// cria uma matriz diagonal n x n
    return malloc (n*sizeof (double));   // usa só n elementos
}

double leMatrizDiagonal (double *M, int i, int j) {
    if (i==j) return M[i];
    return 0.0;
}

Matriz tridiagonal
(a) tamanho do vetor de alocação: 3n – 2
(b) elementos não nulos m(i,j) são tais que |i –j| <= 1
(c) endereçamento ordenada por linhas,m[i, j ] == v[(2*i+ j –2)]

Em código:

double *criaMatrizTridiagonal (int n) {
// cria uma matriz tridiagonal n x n
    return malloc ((3*n-2)*sizeof (double));   // usa só 3n-2 elementos
}

double leMatrizTridiagonal (double *M, int i, int j) {
    if (abs(i-j)<=1) return M[(2*i+j-2)];
    return 0.0;
}


Matriz triangular inferior
a) tamanho do vetor de alocação (supondo matriz quadrada)- Há n^2 elementos na matriz;-Há n elementos na diagonal principal; - Logo, há (n^2+ n) / 2 elementos não nulos.
(b) elementos não nulos: Na triangular superior, m[i,j] == 0 se i < j. Na triangular inferior, m[i,j] == 0 se i>j.
(c) endereçamento:
    Triangular superior ordenada por colunas, m[i, j ] == v[(i^2-i) / 2+ j]
    Triangular inferior ordenada por linhas, m[i, j ] == v[(j^2-j) / 2+ i ]

Em código:

double *criaMatrizTriangularSuperior (int n) {
// cria uma matriz Triangular Superior n x n
    return malloc ((n*(n+1)/2)*sizeof (double));   // usa só (n^2+n)/2 elementos
}

double leMatrizTriangularInferior (double *M, int i, int j) {
    if (i>=j) return M[(i*i-i)/2+j)];
    return 0.0;
}

Nota: usando interfaces e vinculação tardia a chamada dos métodos pode ser unificada e a implementação da estrutura de dados pode ser ocultada, criando uma interface única independente da estrutura subjacente.