Создание алгоритма суммы разреженных матриц в формате CSR

Question

С упаковкой матрицы уже разобрался, мой код:

struct CSR
{
    int *AN;
    int *JA;
    int *IA;
};

CSR create_сsr(int **matrix, int n, int m)
{
    CSR csr;
    int NNZ = number_of_non_zeros;
    int *an = new int[NNZ];
    int *ja = new int[NNZ];
    int *ia = new int[(n + 1)];
    for (int i = 0, k = 0; i < n; i++)
    {
        ia[i] = k;
        for (int j = 0; j < m; j++)
        {
            if (matrix[i][j] != 0)
            {
                an[k] = matrix[i][j];
                ja[k] = j;
                k++;
            }
        }
    }
    ia[n] = NNZ;
    csr.AN = an;
    csr.IA = ia;
    csr.JA = ja;
    return csr;
}

Структура и функция которая из обычной матрицы делает матрицу в формате CSR. number_of_non_zeros заданая мною величина, которая равна floor(n * m * 0.3), чтобы нулей в разреженной матрице было примерно 70%. Помогите с созданием алгоритма суммы.

Answer 1

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

Имея такую функцию, обходим строки в параллель, записывая в результат сумму значений, если индексы столбцов совпали, или значение с меньшим индексом столбца, если не совпали.

Псевдокод умозрительно:

matr A, B, C
for line y:
   ka = A.ia[y]
   kb = B.ia[y]
   while ka < A.ia[y+1] and kb < B.ia[y+1]:
      if A.ja[ka] < B.ja[kb]:
          C.put(A.an[ka++], y, A.ja[ka])
      elseif A.ja[ka] > B.ja[kb]:
          C.put(B.an[kb++], y, B.ja[ka])
      else
          C.put(C.put(B.an[kb++]+A.an[ka++]), y, A.ja[ka])
   //обработать, если есть, остатки строки в A или B
     while ka < A.ia[y+1]:
          C.put(A.an[ka++],y, A.ja[ka])
     while kb < B.ia[y+1]:
          C.put(B.an[kb++], y, B.ja[ka])

БЛОГ НА HUSL

Создание алгоритма суммы разреженных матриц в формате CSR

Ответы (1 шт):