Ajude a manter o site livre, gratuito e sem propagandas. Colabore!
Uma matriz é dita ser esparsa quando ela tem apenas poucos elementos não nulos. A ideia é que os elementos não nulos não precisam ser guardados na memória do computador, gerando um grande benefício na redução da demanda de armazenamento de dados. O desafio está no desenvolvimento de estruturas de dados para a alocação eficiente de tais matrizes, i.e. que sejam suficientemente adequadas para os métodos numéricos conhecidos.
Matrizes esparsas podem ser classificadas como estruturadas ou não-estruturadas. Uma matriz estruturada é aquela em que as entradas não-nulas formam um padrão regular. Por exemplo, estão dispostas em poucas diagonais ou formam blocos (submatrizes densas) ao longo de sua diagonal principal. No caso de não haver um padrão regular das entradas não-nulas, a matriz esparsa é dita ser não-estruturada. Consulte a Figura 1.3 para exemplos.
A esparsidade de uma matriz é a porcentagem de elementos nulos que ela tem, i.e. para uma matriz quadrada tem-se que a esparsidade é
(1.66) |
Por exemplo, a matriz identidade de tamanho tem esparsidade
(1.67) |
A ideia é armazenar apenas os elementos não-nulos de uma matriz esparsa, de forma a economizar a demanda de armazenamento computacional. Cuidados devem ser tomados para que a estrutura de armazenamento utilizada seja adequada para a computação das operações matriciais mais comuns.
O formato COO (do inglês, COOrdinate format) é o esquema de armazenamento simples de matrizes esparsas. As estrutura de dados consiste em três arranjos:
um arranjo contendo as entradas não-nulas da matriz;
um arranjo contendo seus índices de linha;
um arranjo contendo seus índices de coluna.
O método scipy.sparse.coo_array permite a alocação de matrizes no formato COO.
O seguinte código armazena a matriz
(1.68) |
no formato COO.
Vantagens do formato COO
Permite a entrada de dados duplicados (simplicidade).
Conversão rápida para os formatos CSR e CSC.
Desavantagens do formato COO - não suporta diretamente:
operações aritméticas.
fatiamento.
O formato COO permite a entrada duplicada de elementos. Nestes casos, na alocação da coo_array, os elementos duplicados são somados. Por exemplo, considere o seguinte código.
Consideremos a aproximação pelo método de diferenças finitas do problema de Poisson99endnote: 9Siméon Denis Poisson, 1781 - 1840, matemático francês. Fonte: Wikipédia:Siméon Denis Poisson. 2D trabalhado no Exemplo 1.1.3. O seguinte código, faz a alocação da matriz do problema discreto no formato COO. Ao final, o sistema é resolvido usando a função scipy.sparse.linalg.spsolve.
O formato CSR (do inglês, Compressed Sparse Row) é uma variação do COO que busca diminuir a alocação de dados repetidos. Assim como o COO, o formato conta com três arranjos , , :
é o arranjo contendo os elementos não-nulos da matriz, ordenados por linhas (i.e., da esquerda para direita, de cima para baixo);
é o arranjo contendo o índice das colunas das entradas não-nulas da matriz (como no formato COO);
é um arranjo cujos elementos são a posição no arranjo em que cada linha da matriz começa a ser representada. O número de elementos de -ésima linha da matriz dado por .
O método scipy.sparse.csr_array permite a alocação de matrizes no formato CSR.
No Exemplo 1.2.1, alocamos a matriz
(1.69) |
no formato COO. Aqui, vamos converter a alocação para o formato CSR e, então, verificar seus atributos.
d = [ 2. 1. 3. 2. -1. -1. -2. 1.] c = [0 2 1 2 3 1 2 3] p = [0 2 5 7 8]
Por exemplo, o elemento p[i=2] = 5 aponta para o c[k=5] = j = 1, o que fornece A[i=2,j=1] = d[k] = -1.. Verifique!
Vantagens do formato CSR
operações aritméticas eficientes;
fatiamento por linhas eficiente;
multiplicação matriz vetor eficiente.
Desvantagens do formato CSR
fatiamento por colunas não eficiente;
custo elevado de realocação com alteração da esparsidade da matriz.
O formato CSC (do inglês, Compressed Sparse Column) é uma variação análoga do CSR, mas para armazenamento por colunas. O formato conta com três arranjos , , :
é o arranjo contendo os elementos não-nulos da matriz, ordenados por colunas (i.e., de cima para baixo, da esquerda para direita);
é o arranjo contendo o índice das linhas das entradas não-nulas da matriz;
é um arranjo cujos elementos são a posição no arranjo em que cada coluna da matriz começa a ser representada. O número de elementos de -ésima coluna da matriz dado por .
O método scipy.sparse.csc_array permite a alocação de matrizes no formato CSC.
No Exemplo 1.2.1, alocamos a matriz
(1.70) |
no formato COO. Aqui, vamos converter a alocação para o formato CSC e, então, verificar seus atributos.
d = [2. 3. -1. 1. 2. -2. -1. 1.] l = [0 1 2 0 1 2 1 3] p = [0 1 3 6 8]
Assim sendo, o elemento p[j=2] = 3 aponta para o l[k=3] = 0, o que informa que A[i=0,j=2]=d[k]=1.. Verifique!
Vantagens do formato CSC
fatiamento por colunas eficiente;
operações aritméticas eficientes;
multiplicação matriz vetor eficiente1010endnote: 10CSR é mais eficiente em muitos casos..
Desvantagens do formato CSC
fatiamento por linhas não eficiente;
custo elevado de realocação com alteração da esparsidade da matriz.
Além dos formatos COO, CSR e CSC, exitem ainda vários outros que podem empregados e que são mais eficientes em determinadas aplicações. Recomendamos a leitura de [6, Seção 3.4] e da documentação do scipy.sparse.
Considere o seguinte problema de valor de contorno
(1.71) | |||
(1.72) | |||
(1.73) |
para . Assumindo a fonte . Aplique o método de diferenças finitas para computar uma aproximação para a solução do problema. Use diferenças finitas centrais para as derivadas e uma malha uniforme. Use o formato COO para armazenar a matriz do problema discreto . Então, compute sua solução com o método scipy.sparse.linalg.spsolve para matrizes em formato
CSR
CSC
Dica:
Armazene a matriz
(1.74) |
em cada um dos seguintes formatos
COO
CSR
CSC
e, então, adicione o valor ao elemento da segunda linha e terceira coluna.
a)
Considere o seguinte sistema linear
(1.75) | |||
(1.76) | |||
(1.77) | |||
(1.78) |
Armazene sua matriz de coeficientes em formato CSC e compute sua fatoração LU. Então, resolva o sistema usando a fatoração obtida.
Dica: verifique seu resultados com o método scipy.sparse.linalg.splu.
Considere a seguinte equação diferencial parcial de difusão-advecção com condições de contorno de Dirichlet homogêneas
(1.79) |
Aplique o método de diferenças finitas para obter um problema discreto que aproxime a solução. Use os formatos de armazenamento de matrizes esparsas adequados e compute a solução aproximada. Estude cada um dos seguintes casos:
Dica: use fórmulas de diferenças finitas progressiva ou regressiva para aproximar de acordo com o vetor .
Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!
Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.
Ajude a manter o site livre, gratuito e sem propagandas. Colabore!
Uma matriz é dita ser esparsa quando ela tem apenas poucos elementos não nulos. A ideia é que os elementos não nulos não precisam ser guardados na memória do computador, gerando um grande benefício na redução da demanda de armazenamento de dados. O desafio está no desenvolvimento de estruturas de dados para a alocação eficiente de tais matrizes, i.e. que sejam suficientemente adequadas para os métodos numéricos conhecidos.
Matrizes esparsas podem ser classificadas como estruturadas ou não-estruturadas. Uma matriz estruturada é aquela em que as entradas não-nulas formam um padrão regular. Por exemplo, estão dispostas em poucas diagonais ou formam blocos (submatrizes densas) ao longo de sua diagonal principal. No caso de não haver um padrão regular das entradas não-nulas, a matriz esparsa é dita ser não-estruturada. Consulte a Figura 1.3 para exemplos.
A esparsidade de uma matriz é a porcentagem de elementos nulos que ela tem, i.e. para uma matriz quadrada tem-se que a esparsidade é
(1.66) |
Por exemplo, a matriz identidade de tamanho tem esparsidade
(1.67) |
A ideia é armazenar apenas os elementos não-nulos de uma matriz esparsa, de forma a economizar a demanda de armazenamento computacional. Cuidados devem ser tomados para que a estrutura de armazenamento utilizada seja adequada para a computação das operações matriciais mais comuns.
O formato COO (do inglês, COOrdinate format) é o esquema de armazenamento simples de matrizes esparsas. As estrutura de dados consiste em três arranjos:
um arranjo contendo as entradas não-nulas da matriz;
um arranjo contendo seus índices de linha;
um arranjo contendo seus índices de coluna.
O método scipy.sparse.coo_array permite a alocação de matrizes no formato COO.
O seguinte código armazena a matriz
(1.68) |
no formato COO.
Vantagens do formato COO
Permite a entrada de dados duplicados (simplicidade).
Conversão rápida para os formatos CSR e CSC.
Desavantagens do formato COO - não suporta diretamente:
operações aritméticas.
fatiamento.
O formato COO permite a entrada duplicada de elementos. Nestes casos, na alocação da coo_array, os elementos duplicados são somados. Por exemplo, considere o seguinte código.
Consideremos a aproximação pelo método de diferenças finitas do problema de Poisson99endnote: 9Siméon Denis Poisson, 1781 - 1840, matemático francês. Fonte: Wikipédia:Siméon Denis Poisson. 2D trabalhado no Exemplo 1.1.3. O seguinte código, faz a alocação da matriz do problema discreto no formato COO. Ao final, o sistema é resolvido usando a função scipy.sparse.linalg.spsolve.
O formato CSR (do inglês, Compressed Sparse Row) é uma variação do COO que busca diminuir a alocação de dados repetidos. Assim como o COO, o formato conta com três arranjos , , :
é o arranjo contendo os elementos não-nulos da matriz, ordenados por linhas (i.e., da esquerda para direita, de cima para baixo);
é o arranjo contendo o índice das colunas das entradas não-nulas da matriz (como no formato COO);
é um arranjo cujos elementos são a posição no arranjo em que cada linha da matriz começa a ser representada. O número de elementos de -ésima linha da matriz dado por .
O método scipy.sparse.csr_array permite a alocação de matrizes no formato CSR.
No Exemplo 1.2.1, alocamos a matriz
(1.69) |
no formato COO. Aqui, vamos converter a alocação para o formato CSR e, então, verificar seus atributos.
d = [ 2. 1. 3. 2. -1. -1. -2. 1.] c = [0 2 1 2 3 1 2 3] p = [0 2 5 7 8]
Por exemplo, o elemento p[i=2] = 5 aponta para o c[k=5] = j = 1, o que fornece A[i=2,j=1] = d[k] = -1.. Verifique!
Vantagens do formato CSR
operações aritméticas eficientes;
fatiamento por linhas eficiente;
multiplicação matriz vetor eficiente.
Desvantagens do formato CSR
fatiamento por colunas não eficiente;
custo elevado de realocação com alteração da esparsidade da matriz.
O formato CSC (do inglês, Compressed Sparse Column) é uma variação análoga do CSR, mas para armazenamento por colunas. O formato conta com três arranjos , , :
é o arranjo contendo os elementos não-nulos da matriz, ordenados por colunas (i.e., de cima para baixo, da esquerda para direita);
é o arranjo contendo o índice das linhas das entradas não-nulas da matriz;
é um arranjo cujos elementos são a posição no arranjo em que cada coluna da matriz começa a ser representada. O número de elementos de -ésima coluna da matriz dado por .
O método scipy.sparse.csc_array permite a alocação de matrizes no formato CSC.
No Exemplo 1.2.1, alocamos a matriz
(1.70) |
no formato COO. Aqui, vamos converter a alocação para o formato CSC e, então, verificar seus atributos.
d = [2. 3. -1. 1. 2. -2. -1. 1.] l = [0 1 2 0 1 2 1 3] p = [0 1 3 6 8]
Assim sendo, o elemento p[j=2] = 3 aponta para o l[k=3] = 0, o que informa que A[i=0,j=2]=d[k]=1.. Verifique!
Vantagens do formato CSC
fatiamento por colunas eficiente;
operações aritméticas eficientes;
multiplicação matriz vetor eficiente1010endnote: 10CSR é mais eficiente em muitos casos..
Desvantagens do formato CSC
fatiamento por linhas não eficiente;
custo elevado de realocação com alteração da esparsidade da matriz.
Além dos formatos COO, CSR e CSC, exitem ainda vários outros que podem empregados e que são mais eficientes em determinadas aplicações. Recomendamos a leitura de [6, Seção 3.4] e da documentação do scipy.sparse.
Considere o seguinte problema de valor de contorno
(1.71) | |||
(1.72) | |||
(1.73) |
para . Assumindo a fonte . Aplique o método de diferenças finitas para computar uma aproximação para a solução do problema. Use diferenças finitas centrais para as derivadas e uma malha uniforme. Use o formato COO para armazenar a matriz do problema discreto . Então, compute sua solução com o método scipy.sparse.linalg.spsolve para matrizes em formato
CSR
CSC
Dica:
Armazene a matriz
(1.74) |
em cada um dos seguintes formatos
COO
CSR
CSC
e, então, adicione o valor ao elemento da segunda linha e terceira coluna.
a)
Considere o seguinte sistema linear
(1.75) | |||
(1.76) | |||
(1.77) | |||
(1.78) |
Armazene sua matriz de coeficientes em formato CSC e compute sua fatoração LU. Então, resolva o sistema usando a fatoração obtida.
Dica: verifique seu resultados com o método scipy.sparse.linalg.splu.
Considere a seguinte equação diferencial parcial de difusão-advecção com condições de contorno de Dirichlet homogêneas
(1.79) |
Aplique o método de diferenças finitas para obter um problema discreto que aproxime a solução. Use os formatos de armazenamento de matrizes esparsas adequados e compute a solução aproximada. Estude cada um dos seguintes casos:
Dica: use fórmulas de diferenças finitas progressiva ou regressiva para aproximar de acordo com o vetor .
Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!
Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.