Эффективная параллелизация кода в операциях с разреженными матрицами

Abstract

В бакалаврской работе Н.А. Назаров исследовал эффективность работы с разреженными матрицами больших размерностей при организации их хранения в специальных форматах. Во многих областях прикладной математики возникает необходимость работать с сильно разреженными матрицами большого размера, т.е. матрицами, у которых количество ненулевых элементов на несколько порядков меньше, чем общее количество элементов. Хранить и обрабатывать такие матрицы принято в специальных форматах, эффективно упаковывающих матрицу. Однако, хранение в таких форматах влечет за собой усложнение алгоритмов, реализующих операции над матрицами. Интересно также исследовать эффективность распараллеливания и возможности векторизации таких алгоритмов для современных высокопроизводительных архитектур вычислительных систем. В своей бакалаврской работе Н.А. Назаров сравнил два формата хранения разреженных матриц – координатный формат (COO) и формат сжатого хранения по строкам (CRS) по двум критериям – объему занимаемой памяти и эффективности распараллеливания основных операций (транспонирования, умножения матрицы на вектор, и вычисления произведения матриц).