Умножение разреженных матриц в c

У меня есть 2 разреженных файла матрицы в формате матричного рынка:

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]

Спасибо.

2
0
1 811
2

Ответы 2

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

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

Вам даже не нужно преобразовывать формат матрицы. Однако есть способы кормления и в формате триплета.

Другие вопросы по теме