Cómo minimizar el costo de calcular una multiplicación de matrices cuando las matrices tienen muchos ceros

Answer 1

Gracias por a2a

Esta es un área de investigación activa. Los métodos para minimizar el costo dependen en gran medida de la estructura de la matriz. Hay soluciones de computación cuántica que se han desarrollado recientemente y que no cubro aquí, pero sí en otras respuestas de Quora, como otras. Sigue una sinopsis rápida, para formar C = AB:

1. A, B: matriz cuadrada triangular inferior (o superior). Tal matriz tiene ceros arriba (abajo) de la diagonal. El costo de la multiplicación es [matemática] n ^ 3/6 [/ matemática] en lugar de [matemática] n ^ 3. [/ Matemática]
2. A, B: matriz cuadrada bidiagonal. Tal matriz tiene entradas distintas de cero solo en la diagonal y una adyacente fuera de la diagonal directamente arriba o abajo. El costo de la multiplicación es [matemática] 3n [/ matemática] [matemática] [/ matemática] en lugar de [matemática] n ^ 3. [/ Matemática]
3. Una matriz de Fourier: [matemáticas] n ^ 2 log n [/ matemáticas]
4. A Circulante: [matemática] n ^ 2 log n [/ matemática]
5. A y B ambos o circulante: [matemática] 3n log (n) [/ matemática]
6. A o B o ambas matrices cercanas a las formas anteriores: Encuentre una descomposición de la forma [math] A = W + \ epsilon [/ math] de manera que W esté estructurada y [math] \ epsilon [/ math] sea muy escasa.

Hay 6! combinaciones de todo lo anterior (ok, no del todo, ya que 4,5 no son disjuntas). También hay infinitos otros casos especiales menos completos.

Answer 2

Una matriz con ‘muchos ceros’ se llama matriz dispersa .

No soy un experto en la implementación rápida de evaluar el producto de dos matrices dispersas o, de hecho, en el tema de las matrices dispersas en general, pero una simple búsqueda en Google me proporcionó una buena cantidad de enlaces para su lectura.

Google: producto eficiente de matrices dispersas

Uno de los papeles que me llamó la atención es

http://cs.tau.ac.il/~zwick/paper …

que compara varios algoritmos de multiplicación de matrices antes de introducir su propio algoritmo.

Espero que encuentres el algoritmo que se adapte a tus necesidades.

Answer 3

ATA Una de las formas más fáciles de optimizar es aprovechar las filas y columnas que son completamente cero. En una representación escasa indexada por fila o columna, estas ni siquiera están representadas. En [matemáticas] A = BC [/ matemáticas] una fila de todo cero en B produce una fila de todo cero en A. Lo mismo con columnas en C y columnas en A. Usando un índice basado en filas y columnas para B y C respectivamente hace que sea trivial aprovechar esto. Esta es una optimización valiosa en la medida en que las matrices B y C son tan escasas que muchas filas y columnas son cero.

Answer 4

Hay buenas noticias y malas noticias. La mala noticia es que la cantidad de cómputo en términos del número de operaciones sigue siendo la misma, incluso si la matriz tiene muchos ceros.

La cantidad de almacenamiento (memoria) puede reducirse drásticamente si uno elige aplicar matrices dispersas para lidiar con la situación.