SparseMatrix construction in Eigen

Question

Я строю редкую линейную систему с несколькими (мягкими) ограничениями. Я конвертирую код, который использовался для построения матрицы с boost :: ublas, для Eigen. Ускорение: ublas имеет удобный способ создать разреженную матрицу с известным (или оцененным) числом не нулей и имеет достаточно быстрый оператор (int row, int col) для обновления своих элементов.

Проблема заключается в следующем:

• Использование разреженная матрица :: setFromTriplets:
  Моя система имеет много ограничений. Как наивный, «слегка» преувеличенный пример, позвольте сказать, что у меня есть разреженная матрица размером 100x100, с 500 nnz, но 1 миллиард избыточных ограничений (т. Е. Ненулевые коэффициенты изменяются в миллиард раз). setFromTriplets требует от меня хранить 1 миллиард коэффициентов, большинство из которых будет суммировано, чтобы сформировать мой набор из 500 ненулевых коэффициентов. Это не очень эффективно, а не память. Конечно, я могу заменить std :: vector на std :: map и выполнить скопление ограничений вручную, но это как-то не соответствует точке разреженного матричного класса, и это тоже неэффективно.

• Использование SparseMatrix :: insert (i, j, val):
  Не работает, если элемент уже присутствует. Моя проблема состоит в том, чтобы иметь возможность накапливать коэффициенты, которые уже присутствуют.

• Использование SparseMatrix :: coeffRef (i, j):
  Это действительно работает и будет функцией, которую я ищу. Однако это на несколько порядков медленнее, чем boost :: ublas. Я удивлен, что я не видел лучшей функции для этого. Я думал, что это будет связано с количеством ненулевых элементов, которое неизвестно заранее, и вынуждает множественные перераспределения (что и происходит на практике). Однако использование SparseMatrix :: reserve() не имеет никакого эффекта, поскольку это функция, которая работает только для сжатых матриц (комментарий в источнике говорит «« Эта функция не имеет смысла в не сжатом режиме »перед утверждением). .. и, как сказана в документации «введение нового элемента в разреженную матрицу преобразует это позже в несжатом режим».

Что является наиболее эффективным способом для создания разреженной матрицы в Эйгене в то же время способные обновить его коэффициенты несколько раз

Благодарности

[EDIT: пример использования: матрица 10х10 с 10 не-ковавший Операционные системы. Для простоты, матрица является диагональной]

SparseMatrix<double> mat(10, 10); 
for (int i=0; i<10; i++) { 
    for (int j=0; j<1000000; j++) { 
    mat.coeffRef(i, i) += rand()%10; 
    } 
} 

=> работает, но порядки медленнее, чем оператор ublas() (для больших матриц и более реалистичной обстановки, конечно).

std::vector<Eigen::Triplet<double> > triplets(10000000); 
int k=0; 
for (int i=0; i<10; i++) { 
    for (int j=0; j<1000000; j++) { 
    triplets[k++] = Eigen::Triplet<double>(i,i,rand()%10); 
    } 
} 
SparseMatrix<double> mat(10, 10); 
mat.setFromTriplets(triplets.begin(), triplets.end()); 

=> не память дружеская ...

Answer 1

Чтобы insert из coeffRef эффективных, вам необходимо зарезервировать достаточно мест, используя mat.reserve(nnz) где nnz является , содержащим оценочное число ненулевого каждого столбца. Лучше немного переоценить эти цифры, чтобы избежать многочисленных перераспределений/копий. Другим дополнительным трюком является то, что при первом доступе к элементу (i,j) этот элемент является последним из столбца j.

Если вы можете легко вычислить шаблон разреженности, то альтернативой является заполнение вектора уникальной триплета с 0 для значений, а затем coeffRef будет быстрым.