Оптимизация поддержки маски в произведении Кронекера в SuiteSpares:GraphBLAS

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

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

2 курс


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

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


Консультант

Grigorev Semyon


Источник

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