Как умножить две разреженные матрицы в C?

Question

У меня есть разреженная матрица D, и я хочу умножить D_transpose и D, чтобы получить L следующим образом:

L = D '* D;

Я использую sparseBLAS для работы с разреженными матрицами, но documentation говорит, что нечего умножать две разреженные матрицы.

Я полностью застрял и понятия не имею, как действовать.

Размеры D обычно составляют около 500 000 на 250 000. Я не могу назначить столько памяти вообще, так что это просто нужно сделать, используя разреженные матрицы.

Я сделал это с помощью MATLAB, и я не понимаю, как это работает MATLAB, если он также использует sparseBLAS под интерфейсом - или это так? Если нет, что он использует? Я тоже мог бы это использовать.

Благодарим за понимание!

EDIT: Решенный. Мне понадобилась матрица L, чтобы умножить ее на вектор. Поэтому вместо первого вычисления L, я просто сделал D '* (D * x), тем самым избегая необходимости в умножении двух разреженных матриц. Теперь я занимаюсь только разреженной матрицей и плотным векторным мультипликатом, который поддерживается sparseBLAS.

Answer 1

Насколько я понимаю, ваша проблема в основном заключается в хранении огромной матрицы в памяти. Вы можете сохранить значения в паре (строка, столбец). Например,

1 0 0 
0 0 2 
0 4 0 

Этой матрица может быть сохранен в std::map<pair<int, int>, int> как:

map[make_pair(1, 1)] = 1 
map[make_pair(2, 3)] = 2 
map[make_pair(3, 2)] = 4 

Теперь расчетная части. Если предположить, что первая матрица хранится в map1, вторая матрица хранится в map2 и ответ хранится в mapAns,

for each element x in map1: 
    for each element y in map2: 
     if x.column == y.row: 
      mapAns[x.row, y.column] += x.value * y.value 

Вы должны использовать карту как структуру пользовательских данных, если вы хотите сделать то же самое в С.

Answer 2

Фактически это указано в документации.

Page 11

5.2 Использование Sparse BLAS матриц

После того, матрица ручка разреженных BLAS была полностью построена (что-то , что может быть проверена путем проверки свойств blas_valid_handle), можно до используйте матричный дескриптор для выполнения операций. В это время поддерживаются четыре приведенные операции в таблицах 3.2 и 3.3. В дополнение к выполнению операций с матрицей разреженных BLAS можно выполнить , чтобы запросить его свойства через его ручку. В таблице 5.5 перечислены свойства, которые могут быть , полученные путем вызова процедуры получения свойств.

Таблица 3.3 Page 4

USMM разреженная матрица-матрица умножения

Так поддержка, кажется, есть. Я просто не могу найти подпись для функции BLAS_usmm. Может быть, вы можете проверить в заголовках.

Редактировать: Если у вас есть ваши sparseBLas от NIST, вы можете проверить файл blas_sparse_proto.h на функции BLAS_*usmm для подписей и параметров.

/* Level 3 Computational Routines */ 

int BLAS_susmm(enum blas_order_type order, enum blas_trans_type transa, 
    int nrhs, float alpha, blas_sparse_matrix A, const float *b, int ldb, 
     float *c, int ldc); 
int BLAS_dusmm(enum blas_order_type order, enum blas_trans_type transa, 
     int nrhs, double alpha, blas_sparse_matrix A, const double *b, 
     int ldb, double *c, int ldc); 
int BLAS_cusmm(enum blas_order_type order, enum blas_trans_type transa, 
     int nrhs, const void *alpha, blas_sparse_matrix A, const void *b, 
    int ldb, void *c, int ldc); 
int BLAS_zusmm(enum blas_order_type order, enum blas_trans_type transa, 
     int nrhs, const void *alpha, blas_sparse_matrix A, const void *b, 
    int ldb, void *c, int ldc);