Умножение разреженных матриц в 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
Умножать разреженные матрицы - не лучшая идея, потому что результирующая матрица в любом случае будет плотной. Ваш алгоритм, видимо, состоит из последовательного умножения разреженных матриц на вектор: матрица умножается на вектор, затем другая матрица умножается на полученное произведение и так далее. Было бы разумно придерживаться этого вычислительного шаблона, чтобы сэкономить время процессора и объем оперативной памяти (последний будет большим, если вы намереваетесь получить и сохранить продукт двух разреженных матриц).
Есть немногочисленные пакеты, которые делают умножение за вас. Вы пробовали Csparse внутри SuiteSparse? http://faculty.cse.tamu.edu/davis/suitesparse.html
Вам даже не нужно преобразовывать формат матрицы. Однако есть способы кормления и в формате триплета.