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

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

Мне нужно вычесть число с плавающей запятой (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 (матрица, заполненная значениями x):

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 в плотную, которые требуют много памяти в случае очень больших матриц.


c++ eigen sparse-matrix
person Jay    schedule 22.04.2015    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

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

person Avi Ginsburg    schedule 22.04.2015

arrow_upward
1
arrow_downward

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

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

(G-X)*v == (G*v).array()-v.sum()*x
person ggael    schedule 24.04.2015