c++ - producto - operaciones con matrices en c

Rápida multiplicación de matriz escasa

Question

para la clase tengo que escribir mi propio solucionador de ecuaciones lineales para matrices dispersas. Soy libre de usar cualquier tipo de estructura de datos para matrices dispersas y tengo que implementar varias soluciones, incluido el gradiente de conjugación.

Me preguntaba si existe una manera famosa de almacenar matrices dispersas de manera que la multiplicación con un vector sea relativamente rápida.

En este momento, mis matrices dispersas se implementan básicamente con std::map< std::pair<int, int>, double> que almacena los datos, si los hay. Esto transforma la multiplicación de una matriz con un vector en una complejidad O (n²) a una O (n²log (n)) ya que tengo que realizar una búsqueda para cada elemento de la matriz. He analizado el formato de matriz dispersa de Yale y parece que la recuperación de un elemento también está en O (log (n)), por lo que no estoy seguro de si sería mucho más rápido.

Como referencia, tengo una matriz de 800x800 que está poblada con 5000 entradas. Se requieren aproximadamente 450 segundos para resolver dicho sistema con el método de gradiente conjugado.

¿Crees que es posible hacerlo mucho más rápido con otra estructura de datos?

¡Gracias!

Answer 1

Las opciones más comunes son el almacenamiento CSC o CSR . Ambos son eficientes para la multiplicación de matriz-vector. También es muy fácil codificar esas rutinas de multiplicación, si tiene que hacerlo usted mismo.

Dicho esto, el almacenamiento de Yale también produce una multiplicación matriz-vector muy eficiente. Si está realizando la búsqueda de elementos de matriz, ha entendido mal cómo usar el formato. Sugiero que estudies algunas de las bibliotecas dispersas estándar para aprender cómo se implementa la multiplicación matriz-vector.

Incluso con su almacenamiento actual puede realizar la multiplicación de la matriz en O (n) complejidad. Todos los escasos algoritmos de multiplicación matriz-vector que he visto se reducen a los mismos pasos. Por ejemplo, considere y = Ax.

1. Zeroise el vector de resultado, y.
2. Inicialice un iterador para los elementos distintos de cero de la matriz, A.
3. Obtenga el siguiente elemento distinto de cero de la matriz, decir A [i, j]. Tenga en cuenta que el patrón de i, j no sigue un patrón regular. Simplemente refleja el orden en que se almacenan los elementos distintos de cero de A.
4. y [i] + = A [i, j] * x [j]
5. Si hay más elementos de A, goto 3.

Sospecho que estás escribiendo el doble clásico para el código de multiplicación de bucle denso:

for (i=0; i<N; i++)
for (j=0; j<N; j++)
y[i] += A[i,j]*x[j]

y eso es lo que te está llevando a realizar búsquedas.

Pero no estoy sugiriendo que se quede con su almacenamiento std::map . Eso no va a ser muy eficiente. Recomendaría CSC principalmente porque es el más utilizado.