Преобразование COO в формат CSR в С++

У меня есть матрица в формате COO. Точнее, есть три матрицы row_index, column_index, value. Не могли бы вы помочь мне преобразовать этот формат матрицы в CSR формат с эффективный, не затратный в вычислительном отношении способ, используя язык C? Существуют ли библиотеки для этой цели?

Пример:

введите здесь описание изображения

Формат главного операционного директора:

       row_index col_index value
          1         1         1
          1         2        -1
          1         3        -3   
          2         1        -2
          2         2         5
          3         3         4
          3         4         6
          3         5         4
          4         1        -4
          4         3         2
          4         4         7     
          5         2         8
          5         5        -5

c sparse-matrix intel-mkl
person Thoth    schedule 10.05.2014    source источник

Ответы (3)


arrow_upward
2
arrow_downward

документация Intel MKL (для mkl_csrcoo) указывает:

Преобразует разреженную матрицу в формате CSR в формат координат и наоборот.

И по приведенной выше ссылке вы должны установить job:

if job(1)=1, the matrix in the coordinate format is converted to the CSR format.

person boxed__l    schedule 10.05.2014

arrow_upward
3
arrow_downward

Я знаю, что это старый поток, но, предполагая, что данные COO (i,j) упорядочены/отсортированы, как вы показываете, последовательный алгоритм преобразования из COO в CSR:

int main()
{
    // Example from Wikipedia (https://en.wikipedia.org/wiki/Sparse_matrix)

    // Matrix:
    // 10 20  0  0  0  0
    //  0 30  0 40  0  0
    //  0  0 50 60 70  0
    //  0  0  0  0  0 80

    // Expected output:
    // csr_val: 10 20 30 40 50 60 70 80
    // csr_col:  0  1  1  3  2  3  4  5
    // csr_row:  0  2  4  7  8

    const int  nnz = 8; // number of non-zero elements
    const int rows = 4; // number of matrix rows
    const int cols = 6; // number of matrix columns

    // coo data:
    double coo_val[nnz] = { 10.0, 20.0, 30.0, 40.0, 50.0, 60.0, 70.0, 80.0 };
    int    coo_row[nnz] = { 0, 0, 1, 1, 2, 2, 2, 3 };
    int    coo_col[nnz] = { 0, 1, 1, 3, 2, 3, 4, 5 };

    // coo to csr:
    double csr_val[nnz]      = { 0 };
    int    csr_col[nnz]      = { 0 };
    int    csr_row[rows + 1] = { 0 };
    for (int i = 0; i < nnz; i++)
    {
        csr_val[i] = coo_val[i];
        csr_col[i] = coo_col[i];
        csr_row[coo_row[i] + 1]++;
    }
    for (int i = 0; i < rows; i++)
    {
        csr_row[i + 1] += csr_row[i];
    }
}

Обратите внимание, что, предполагая, что данные COO (i,j) упорядочены/отсортированы, csr_col = coo_col и csr_val = coo_val, вам просто нужно получить csr_row, а это так же просто, как:

int csr_row[rows + 1] = { 0 };
for (int i = 0; i < nnz; i++)
    csr_row[coo_row[i] + 1]++;
for (int i = 0; i < rows; i++)
    csr_row[i + 1] += csr_row[i];

Итак, в заключение, вы можете легко добиться того, чего хотите, с помощью 5 строк кода, представленных выше.

Последнее примечание:

Предлагаемый метод не учитывает повторяющиеся записи COO.

person Carlos    schedule 19.08.2020

arrow_upward
1
arrow_downward

Реализация этого преобразования включена в scipy (с открытым исходным кодом: под лицензией BSD), функция coo_tocsr в частности. Это на C++, но это только для того, чтобы шаблонировать типы данных и индексов, а также для того, чтобы инициализировать структуру данных, чтобы ее можно было легко преобразовать в код C.

person joeln    schedule 11.05.2014