Matrizes esparsas

Guardar só o que não é zero

Muitas matrizes grandes são quase só zeros. Uma malha para precificar uma opção tem uma linha por nível de preço, e cada linha toca só suas duas vizinhas. Uma matriz assim é chamada esparsa. Guardar cada zero desperdiça memória e tempo. O scipy.sparse guarda só as entradas não nulas. O formato csr_matrix (linha esparsa comprimida) usa três listas. data guarda os valores não nulos linha a linha, indices a coluna de cada valor, e indptr diz onde cada linha começa e termina em data: a linha $i$ é data[indptr[i]:indptr[i+1]]. O último número de indptr é a contagem de não nulos, nnz.

Formatos diferentes servem a tarefas diferentes. coo_matrix guarda simples trincas (linha, coluna, valor) e é o jeito fácil de construir uma matriz. csr_matrix é rápido para fatias de linhas e para o produto $A\mathbf x$, que custa cerca de nnz multiplicações em vez de $n^2$. csc_matrix é a mesma ideia por colunas, e dia_matrix guarda diagonais, ideal para matrizes em banda. Para um sistema $A\mathbf x=\mathbf b$, sparse.linalg.spsolve usa os zeros para ser muito mais rápido que uma resolução densa. Esparso nem sempre é melhor: se mais de um terço das entradas é não nulo, a contabilidade custa mais do que poupa. Em finanças, a esparsidade aparece em malhas de precificação, em modelos de fatores em que a maioria das exposições é zero e quando só se mantêm as correlações fortes.

• Três listas: data, indices e indptr descrevem uma matriz CSR, e indptr[-1] é o número de não nulos.
• Construa em COO, calcule em CSR: trincas são fáceis de montar, o armazenamento por linhas é rápido para produtos e resoluções.
• Esparso só compensa se for em sua maioria zeros: uma matriz densa é melhor quando muitas entradas são não nulas.

Lab: o que é avaliado

• Contar os não nulos10 pts
• Quantos valores há numa linha10 pts
• A densidade de uma malha10 pts
• Um produto esparso15 pts
• Qual formato para qual tarefa15 pts
• Um sistema tridiagonal10 pts
• Quando o esparso compensa e quando não30 pts