Курсовая работа: Произведение Кронекера в GraphBLAS-sharp

Оглавление

4.1. CSR → CSR → COO с использованием алгоритма Merge Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.2. CSR → CSR → LIL с конвертацией исходных матриц в LIL 10

4.3. CSR → CSR → COO с преподсчетом размера . . . . . . . 10

4.4. Вывод.............................. 11














2

• Введение

Использование линейной алгебры — один из способов высокопроиз-водительного анализа графов. Графы представляются в виде матриц смежности, которые, зачастую, имеют небольшую плотность, в таком случае, в памяти компьютера их удобно представлять в виде разрежен-ных матриц, используя координатный¹ или CSR²форматы. Множество преобразований графов выражаются в виде операций над соответству-ющими им матрицами смежности. Стандарт GraphBLAS³ определяет базовые структуры и функции для вычисления данных операций.

Одна из базовых операций спецификации — произведение Кронеке-ра⁴ — используется для генерации графов, например, в Графах Кроне-кера [3] — конструкции, которая генерирует множество графов, при-нимая на вход начальный граф и повторно применяя произведения Кронекера, сохраняя результат на каждой итерации. Помимо этого, произведение Кронекера используется в алгоритмах для выполнения контекстно-свободных запросов [1, 5] при построении пересечения двух автоматов.

Несмотря на явное наличие сферы применения, произведение Кро-некера отсутствует во многих реализациях стандарта GraphBLAS. При-чиной этому, вероятно, служит сложность размещения в памяти ре-зультирующей матрицы, ведь ее размер равен произведению размеров входных матриц. А из-за того, что операции кастомизируются пользо-вателем, априори неизвестно, каков будет результат при оперировании

• неявными нулями. Это сильно усложняет подсчет позиций элементов в результирующей матрице.

GraphBLAS-sharp⁵ — одна из реализаций