¿Se puede tratar una matriz como dispersa si tiene muchas entradas relativamente muy pequeñas?

Answer 1

Si hay muchas entradas distintas de cero, no es escasa, por pequeñas que sean. Debe almacenar esas entradas y debe incluirlas en los cálculos, lo que significa que el uso de un código de matriz disperso probablemente no proporcionará una gran mejora, o incluso puede empeorar las cosas.

Dicho esto, puede ser una aproximación válida tirar las pequeñas entradas por completo y reemplazarlas con ceros, en cuyo caso terminará con una matriz dispersa. Es difícil decirlo en general, pero tenga en cuenta que la precisión de la máquina generalmente es de alrededor de 16 decimales, por lo que en la práctica 1 = 1 + 10 ^ -16. Por lo tanto, las entradas de menos de 10 ^ -16 de las más grandes probablemente se descarten de todos modos en el curso de sumar y multiplicar, y es una apuesta bastante segura descartarlas de manera preventiva. Si el cálculo completo es posible (a pesar de que puede llevar mucho tiempo), probablemente debería experimentar con diferentes umbrales para ver si arrojar valores pequeños y usar matrices dispersas acelera las cosas mientras mantiene una precisión aceptable.

Answer 2

Esta es una pregunta bastante interesante. Si su matriz contiene enteros, entonces puede obtener algo de rendimiento combinando múltiples elementos de matriz en una sola palabra y explotando el paralelismo a nivel de palabra.

Si puede usar un algoritmo aproximado, entonces tiene más opciones. Por ejemplo, este documento (Página en technion.ac.il) presenta un algoritmo simple para esparcir una matriz. Su enfoque es doble: dispersa la matriz al establecer aleatoriamente algunos elementos de matriz pequeños en 0 y cuantifica los otros elementos de matriz pequeños para reducir el espacio (lo que puede mejorar el rendimiento de cualquier algoritmo de multiplicación de matriz disperso que eventualmente use). Dada una matriz n por n [matemática] A [/ matemática] y [matemática] \ epsilon> 0 [/ matemática], el algoritmo de dispersión transforma los elementos de matriz [matemática] A_ {i, j} [/ matemática] cuyo valor absoluto es menor que [math] \ epsilon / \ sqrt {n} [/ math] a [math] signo (A_ {i, j}) \ cdot \ epsilon / \ sqrt {n} [/ math] con probabilidad [math] \ sqrt {n} | A_ {i, j} | / \ epsilon [/ math], y a [math] 0 [/ math] de lo contrario. La distancia [matemática] l_ {2} [/ matemática] entre la matriz dispersa y la matriz original será [matemática] O (\ epsilon) [/ matemática] con alta probabilidad.

Una vez que haya calculado las aproximaciones dispersas de sus matrices, puede aplicar técnicas estándar para la multiplicación de matrices dispersas.