#ifndef rdo_sparse_matrix_H #define rdo_sparse_matrix_H /* Álgebra linear com matrizes esparsas. */ #define rdo_sparse_matrix_H_COPYRIGHT "Copyright © 2008 Danillo Pereira e J. Stolfi, UNICAMP" /* Last edited on 2008-07-22 11:25:11 by stolfi */ #define _GNU_SOURCE #include #include typedef struct EntradaDeMatriz { int lin; int col; double valor; } EntradaDeMatriz; /* Tipo de um elemento armazenado explicitamente em uma matriz esparsa. */ typedef struct MatrizEsparsa { uint32_t nlin; //número de linhas na matriz (expandida). uint32_t ncol; //número de colunas da matriz (expandida). uint32_t nen; //número de entradas armazenados. EntradaDeMatriz *e; //vetor com as entradas armazenados. } MatrizEsparsa; /* Tipo do registro-cabeça de uma matriz esparsa {A}, cuja forma expandida tem {nlin} linhas e {ncol} colunas. As entradas estão em {A.e[0..A.nen-1]}. Alguns procedimentos abaixo supõem que as entradas estão ordenadas por linha; alguns supõem que apenas uma parte do vetor {A.e} está ocupada. */ MatrizEsparsa AlocaMatrizEsparsa(int nlin, int ncol, int nen); /* Cria o registro-cabeça de uma matriz esparsa com {nlin} linhas e {ncol} colunas, e aloca o vetor de entradas com espaço para {nen} entradas. */ void DesalocaMatrizEsparsa(MatrizEsparsa *A); /* Libera o espaço usado pela matriz esparsa {A} (menos o cabeçalho {*A}). */ void ExpandeMatrizEsparsa(MatrizEsparsa *A, int pos); /* Garante que a entrada {A->e[pos]} existe. Ou seja: se {pos < A->nen}, não faz nada. Senão realoca o vetor {A->e} de modo ater pelo menos {pos+1} entradas, preservando seu conteúdo atual, e atualiza {A->e,A->nen}. O incremento é geométrico de modo a manter o custo amortizado proporcional a {A->nen}. */ void AjustaTamanhoDeMatrizEsparsa(MatrizEsparsa *A, int nen); /* Garante que o vetor {A->e} tem exatamente {nen} entradas. Ou seja: se {nen == A->nen}, não faz nada. Senão realoca o vetor {A->e} de modo a ter exatamente {nen} entradas, preservando o conteúdo atual das entradas {A->e[0..nen-1]}, e atualiza {A->e,A->nen}. */ int AcrescentaEntradaAMatrizEsparsa(MatrizEsparsa *A, int pos, int lin, int col, double v); /* Se {v} não é zero, acrescenta a entrada com índices {lin,col} e valor {v} à matriz {A}, na posição {pos} do vetor de entradas, e devolve {pos+1}. Se essa entrada não existir (isto é, se {pos >= A->nen}), expande o vetor {A->e}, preservando seu conteúdo e atualizando {A->nen}, de modo que a entrada {A->[pos]} exista. Se {v} for zero, não altera {A} e devolve o próprio {pos}. Supõe que não existe nenhuma entrada com índices {lin,col} na matriz {A}. */ int AcrescentaLinhaAMatrizEsparsa(MatrizEsparsa *A, int pos, int lin, double v[]); /* Considera que {v[0..A->ncol-1]} é uma linha a ser acrescentada à matriz {A}, com índice {lin} na matriz expandida. Acrescenta efetivamente a {A} apenas as entradas {v[j]} não nulas do vetor (com {.lin = lin} e {.col = j}), a partir da posição {pos} no vetor {A->e}. Se não houver espaço suficiente no vetor {A->e}, expande {A->e}, preservando seu conteúdo e atualizando {A->nen}. Devolve como resultado a posição da entrada de {A->e} seguinte à da última entrada efetivamente acrescentada. Supõe que não existe na matriz {A} nenhuma entrada com os mesmos índices das entradas acresscentadas. */ int AcrescentaColunaAMatrizEsparsa(MatrizEsparsa *A, int pos, int col, double v[]); /* Análogo a {AcrescentaLinhaAMatrizEsparsa}, mas considera que {v[0..A->nlin-1]} é a nova coluna {col} da matriz expandida. */ void CopiaMatrizEsparsa(MatrizEsparsa *A, MatrizEsparsa *B); /* Copia as entradas da matriz esparsa {*A} para {*B}. Libera o vetor de entradas de {B} (se houver) e aloca um novo vetor {B=>e} com o tamanho justo. Também copia os campos {nlin} e {ncol}. */ void MultiplicaMatrizEsparsaPorVetor(MatrizEsparsa *A, double b[], double c[]); /* Multiplica a matriz {A} pelo vetor coluna {b[0..n-1]} colocando o resultado em {c[0..m-1]}; onde {m == A->nlin} e {n == A->ncol}. */ void MultiplicaVetorPorMatrizEsparsa(double b[], MatrizEsparsa *A, double c[]); /* Multiplica o vetor linha {b[0..m-1]} pela matriz {A}, colocando o resultado em {c[0..n-1]}; onde {m == A->nlin} e {n == A->ncol}. */ void MultiplicaMatrizesEsparsas(MatrizEsparsa *A, MatrizEsparsa *B, MatrizEsparsa *C); /* Multiplica a matriz esparsa {A} pela matriz esparsa {B} colocando o resultado na matriz {C}. O conteúdo anterior de {C} é descartado e seu vetor de entradas é realocado conforme necessário para ter o tamanho justo. O número de colunas de {A} (na forma expandida) deve ser igual ao número de linhas de {B} (idem). O vetor {A->e} deve estar ordenado de modo que todas as entradas da mesma linha estejam em posições consecutivas. */ int ExtraiLinhaDeMatrizEsparsa(MatrizEsparsa *A, int pos, int lin, double v[]); /* Extrai uma linha {lin} da matriz esparsa {A} e coloca-a em {v[0..n-1]}, onde {n == A->ncols}. Supõe que o vetor de entradas {A->e} está ordenado de tal forma que todos as entradas dessa linha (se houver) estão em posições consecutivas no vetor {A->e}, começando na posição {pos}. Se {pos >= A->nen} ou a entrada {A->e[pos]} não pertence à linha {lin}, supõe que todos so elementos são nulos. As entradas da linha são colocadas no vetor {v[0..A->ncol-1]}; cada entrada com {.col = j} é colocada em {v[j]}, e as demais entradas de {v} são zerados. Devolve a posição no vetor de entradas imediatamente seguinte ao final da linha. */ int ExtraiColunaDeMatrizEsparsa(MatrizEsparsa *A, int pos, int col, double v[]); /* Análogo a {ExtraiLinhaDeMatrizEsparsa}, mas supõe que todas as entradas da coluna {col} a extrair estão em posições consecutivas de {A->e}, começando na posição {pos}. A coluna extraída é colocada em {v[0..m-1]} onde {m == A->nlin}. */ void OrdenaMatrizEsparsaPorLinhas(MatrizEsparsa *A); /* Ordena as entradas da matriz esparsa {A} de modo que todos as entradas de cada linha estejam em posições consecutivas no vetor {A->e}, em ordem crescente do índice da linha. */ void OrdenaMatrizEsparsaPorLinhas(MatrizEsparsa *A); /* Ordena as entradas da matriz esparsa {A} de modo que todos as entradas de cada coluna estejam em posições consecutivas no vetor {A->e}, em ordem crescente do índice da coluna. */ void EscreveMatrizEsparsa(FILE *wr, MatrizEsparsa *A); /* Escreve a matriz esparsa {A} no arquivo {wr}. */ MatrizEsparsa LeMatrizEsparsa(FILE *rd); /* Lê uma matriz esparsa do arquivo {rd}, no formato produzido por {EscreveMatrizEsparsa}. */ #endif