Multiplicación lenta de matrices y vectores dispersos de uBLAS

Question

Estoy convirtiendo parte de mi propio código de álgebra vectorial para usar la biblioteca boost uBLAS optimizada.Sin embargo, cuando intenté hacer una multiplicación SymmetricMatrix-SparseVector descubrí que era aproximadamente 4 veces más lenta que mi propia implementación.El tamaño del vector suele estar entre 0 y 500 y entre el 70 y el 80 % de las entradas son cero.

Aquí está mi código.

void CRoutines::GetA(double a[], double vectorIn[], int sparseVectorIndexes[], int vectorLength, int sparseLength)
{
    compressed_vector<double> inVec (vectorLength, sparseLength);
    for(int i = 0; i < sparseLength; i++)
    {
        inVec(sparseVectorIndexes[i]) = vectorIn[sparseVectorIndexes[i]];
    }
    vector<double> test = prod(inVec, matrix);
        for(int i = 0; i < vectorLength; i++)
    {
        a[i] = test(i);
    }
}

sparseVectorIndexes almacena los índices de los valores distintos de cero del vector de entrada, vectorLength es la longitud del vector y sparseLength es el número de valores distintos de ceros en el vector.La matriz se almacena como una matriz simétrica. symmetric_matrix<double, lower>.

Mi propia implementación es una iteración de bucle anidado simple donde la matriz es solo una matriz doble 2D:

void CRoutines::GetA(double a[], double vectorIn[], int sparseVectorIndexes[], int vectorLength, int sparseLength)
 {
    for (int i = 0; i < vectorLength; i++)
    {
            double temp = 0;

            for (int j = 0; j < sparseLength; j++)
            {
                int row = sparseVectorIndexes[j];
                if (row <= i) // Handle lower triangular sparseness
                    temp += matrix[i][row] * vectorIn[row];
                else
                    temp += matrix[row][i] * vectorIn[row];
            }
            a[i] = temp;
    }

}

¿Por qué uBLAS es 4 veces más lento?¿No estoy escribiendo correctamente la multiplicación?¿O hay otra biblioteca más adecuada para esto?

EDITAR: Si uso una matriz vectorial densa, entonces uBLAS es solo 2 veces más lento...

Answer 1

uBlas no fue diseñado teniendo en mente el rendimiento como objetivo número uno.Hay bibliotecas que son significativamente más rápidas que uBlas.Véase, por ejemplo. http://eigen.tuxfamily.org/index.php?title=Benchmark

Answer 2

este pdf tiene una comparación bastante detallada de varias bibliotecas de álgebra lineal.Me encontré con esto en esta respuesta de Intercambio de pilas de ciencia computacional, que posiblemente sea un mejor lugar para este tipo de preguntas.

Answer 3

No estoy seguro de si es la causa de la desaceleración (¿hiciste un perfil para obtener tu número 4x?), pero este bucle podría ser lento:

for(int i = 0; i < vectorLength; i++)
    {
        a[i] = test(i);
    }

Si se dedica la mayor parte del tiempo a procesar los bucles en su código, entonces este bucle adicional podría duplicar el tiempo (y no tiene nada que ver con ublas).Yo recomendaría usar std::copy en cambio:

std::copy(test.begin(), test.end(), a[0])

La mayoría de los compiladores deberían ver que esto es copiar un doble y hacer una copia óptima, lo que podría solucionar su problema de alguna manera.