Интеграция селектора в произведение Кронекера в SuiteSparse:GraphBLAS

Произведение Кронекера может использоваться для построения пересечения конечных автоматов, которое возникает в различных алгоритмах анализа графов. Проблема заключается в том, что размер такого произведения обычно очень большой, но часть информации — нули, которые можно было бы выкинуть ещё на этапе вычисления произведения. Для такой фильтрации можно использовать произвольный предикат, однако в SuiteSparse:GraphBLAS такая возможность не предусмотрена. В рамках работы предлагается исправить этот недочёт: предложить дизайн API и реализацию, позволяющие использовать фильтр в произведении Кронекера. Результатом, кроме экспериментов, демонстрирующих улучшение потребления памяти, должен стать реквест в SuiteSparse:GraphBLAS.

Требования к студенту
  • Отличное знание языка программирования Си и соответствующего инструментария разработчика (сборка, отладка, тестирование, профилирование).
  • Знание основ линейной алгебры: матрицы, вектора, операции над ними.
Уровень

2 курс


Руководитель

Григорьев Семен Вячеславович


Консультант

Grigorev Semyon


Источник

Кафедра системного программирования СПбГУ