Анализ эффективности использования специальных форматов хранения при параллельном выполнении операций с разреженными матрицами

Abstract

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