Узкое место производительности в программе Eigen

Question

Как часть более крупной проблемы, я сталкиваюсь с горлышком бутылки производительности при работе с разреженными матрицами в Эйгене.

Мне нужно вычесть число с плавающей запятой (x) из каждого элемента в разреженной матрице (G), включая позиции, где коэффициенты равны нулю. Таким образом, нулевые элементы должны иметь значение -x

так, как я это на данный момент выглядит следующим образом:

//calculate G 
x=0.01; 
for(int i=0;i<rows;i++){ 
    for (int j=0; j<cols; j++) { 
     G.coeffRef(i, j) -= x; 
    } 
} 

Когда размер G велик, это простой расчет является узким местом.

Я также попытался преобразовать разреженную матрицу G в плотную один и вычитает P (матрица заполняется значениями х):

MatrixXd DenseG=MatrixXd(G); 
x=0.01; 
for(int i=0;i<rows;i++){ 
    for (int j=0; j<cols; j++) { 
     DenseG(i, j) -= x; 
    } 
} 

Этот метод намного быстрее. Тем не менее, мне просто интересно, есть ли другие обходные пути, которые не связаны с преобразованием G в плотный, что требует большой памяти в случае очень больших матриц.

Answer 1

Ваш «разреженный» расчет эффективно является плотным, поскольку вы вычитаете из всех элементов n^2. Основное различие заключается в том, что вместо того, чтобы выполнять одну операцию на полосе памяти, вам приходится выделять память для матрицы почти каждый раз, когда вы обращаетесь к нулевому элементу. В общем случае разреженные матрицы эффективны, когда они разрежены, и для большинства операций накладываются большие накладные расходы. Эти накладные расходы уравновешиваются только наличием очень небольшого количества элементов и, следовательно, несколько раз повторяют операции.

Другой возможный вариант - воспользоваться Eigen's lazy evaluation, но этот вид зависит от ваших точных требований, которые вы здесь не указали.

Answer 2

Как сказал Ави Гинзбург, эта операция приводит к плотной матрице потери все структуры, где G-XG является начальной разреженной матрицей и X является абстрактной плотной матрицей заполнен x.

Я бы порекомендовал вам попытаться сохранить эти два члена в остальной части вашего алгоритма и обновить математику, чтобы использовать эту специальную структуру. Например, если следующий шаг состоит в том, чтобы умножить его на плотный вектор v, вы можете с пользой использовать его:

(G-X)*v == (G*v).array()-v.sum()*x