Размножение разреженных матриц в C

Question

У меня есть 2 разреженных файла матрицы в формате matrix-market:

row col val
1   1   3.0
1   2   1.0
2   3   2.0
etc...

В настоящее время я разбил файлы на 6 массивов:

row_A[], col_A[], val_A[], row_B[] …

Которые содержат индекс строки, индекс столбца и значение соответственно.

Я хотел бы легко умножить две матрицы без необходимости сначала преобразовывать их в формат плотной матрицы. Есть ли алгоритм для этого?

Я нашел этот псевдокод на Quora, но я не уверен, что это лучшая реализация, или как он будет реализован в C: https://www.quora.com/What-is-the-C-program-for-the-multiplication-of-two-sparse-matrices

multiply(A,B):
  for r in A.rows:
    for c in A.rows[r]:
      for k in B.rows[c]:
        C[r,k] += A[r,c]*B[c,k]

Спасибо.

Answer 1

Есть редкие пакеты, которые делают умножение для вас.Вы пробовали Csparse внутри SuiteSparse?http://faculty.cse.tamu.edu/davis/suitesparse.html

Вам даже не нужно конвертировать матричный формат.Тем не менее, существуют способы подачи в триплетном формате.

Answer 2

Неуместно умножать разреженные матрицы, потому что получающаяся матрица будет плотной в любом случае. Ваш алгоритм, по-видимому, состоит из последовательного умножения разреженных матриц на вектор: матрица умножается на вектор, затем другая матрица умножается на полученный продукт и так далее. Было бы разумно придерживаться этой схемы вычислений, тем самым экономя время ЦП и объем ОЗУ (последний будет большим, если вы собираетесь получить и сохранить произведение двух разреженных матриц).