Алгоритмы алгебры разреженных матриц и их высокопроизводительные реализации

Краткое описание

Алгебра разреженных матриц (Sparse algebra) – важный раздел математики, имеющий очевидное практическое применение. Разреженные матрицы возникают естественным образом при постановке и решении задач из многих научных и инженерных областей. Эффективные методы хранения и обработки таких матриц в современных параллельных вычислительных системах вызывают интерес у широкого круга исследователей.

Одной из актуальных проблем алгебры разреженных матриц является разработка методов решения систем линейных алгебраических уравнений (СЛАУ) Ax = b с разреженной симметричной положительно определенной матрицей A. Решение подобных систем лежит в основе многих вычислительных задач компьютерной алгебры и моделирования физических процессов, в частности, при использовании конечно-элементных методов для численного решения уравнений в частных производных.

Группа занимается разработкой алгоритмов и программных средств для численного решения больших разреженных СЛАУ, а также программной реализацией алгоритмов по обработке разреженных матриц.

Коллектив

Руководитель проекта

Участники проекта

  • Козинов Е.А., преподаватель каф. МОСТ, ИИТММ ННГУ
  • Пирова А.Ю., преподаватель каф. МОСТ, ИИТММ ННГУ

Ранее в проекте участвовали

  • Сысоев А.В., к.т.н., ст.преп. каф. МОСТ, ИИТММ ННГУ
  • Лебедев С.А., аспирант каф. МОСТ, ИИТММ ННГУ
  • Ахмеджанов Д.Р., магистрант, ИИТММ ННГУ
  • Байкова К.В., студент, ИИТММ ННГУ
  • Гвоздева В., магистрант, ИИТММ ННГУ
  • Горохов Д.С., магистрант, ИИТММ ННГУ
  • Кудрявцев Н.Ю., магистрант, ИИТММ ННГУ
  • Лебедев И.Г., преподаватель, ИИТММ ННГУ
  • Миронова А., магистрант, ИИТММ ННГУ
  • Новак А., магистрант, ИИТММ ННГУ
  • Носова С.А., аспирант каф. МОСТ, ИИТММ ННГУ
  • Парамузов В.В., магистрант, ИИТММ ННГУ
  • Филиппенко С.С., магистрант каф. МОЭВМ, ВМК ННГУ
  • Клян С.А., магистрант каф. МОЭВМ, ВМК ННГУ
  • Рыжов С.А., магистрант каф. ИАНИ, ВМК ННГУ
  • Шульгина Я.О., магистрант каф. МОСТ, ИИТММ ННГУ

Участники проекта благодарят наших коллег Бартенева Ю.Г., Бастракова С.И., Гергеля В.П., Линева А.В., Осипова Г.В., Прилуцкого М.Х., Старостина Н.В. за полезные обсуждения и внимание к работе.

Основные результаты

  1. Разработана библиотека для переупорядочения разреженных матриц с целью уменьшения заполнения фактора Холецкого. Переупорядочение выполняется модифицированным многоуровневым методом вложенных сечений. Представлены реализации для систем с общей памятью и распределенной памятью, сопоставимые по качеству (размеру фактора) и скорости решения задач с широко распространенными реализациями METIS и Scotch. ПО доступнодля скачивания и использования.
  2. Разработан прямой решатель разреженных СЛАУ. Предложен двухуровневый способ распараллеливания мультифронтального метода разложения Холецкого для систем с общей памятью. Показаны результаты, сопоставимые по скорости с реализацией из библиотеки Intel MKL. Разработанные параллельные алгоритмы выполнены с использованием технологий TBB и OpenMP.
  3. Примеры магистерских работ:
    • Реализация алгоритма подсчета треугольников в графе на основе алгоритма умножения матриц. Параллельная реализация выполнена с использованием библиотеки TBB.
    • Разработка решателя СЛАУ с прямоугольной разреженной матрицей на основе QR-разложения.
    • Разработка решателя СЛАУ с несимметричной разреженной матрицей на основе LU-разложения.
    • Разработка параллельного алгоритма символьной фазы разложения Холецкого.
    • Сравнение алгоритмов умножения разреженных матриц в различных форматах для CPU и Xeon Phi.
  4. Интеграция с другими проектами:
  • Решатель разреженных СЛАУ интегрирован в программный комплекс «Виртуальное сердце», разрабатываемый на каф.ТУиДС института ИТММ ННГУ.
  • Выполнена оптимизация решателя MUMPSдля сокращения времени счета при решении задач с матрицами специального вида.

Избранные публикации

  1. Пирова А.Ю. Новый курс по параллельной обработке графов // Суперкомпьютерные дни в России: Труды международной конференции. Москва: МАКС Пресс, 2020. – 172 с. 2020. С. 129-130. 
  2. Пирова А.Ю., Нестеров А.Ю., Оболенский А.А., Девликамов В.В. Сравнение алгоритмов огрубления графа в задаче параллельного переупорядочения разреженной матрицы // Суперкомпьютерные дни в России: Труды международной конференции. Москва: МАКС Пресс, 2020. – 172 с. 2020. С. 142-143. 
  3. Povelikin R., Lebedev S., Meyerov I. Multithreaded Multifrontal Sparse Cholesky Factorization Using Threading Building Blocks //Russian Supercomputing Days. – Springer, Cham, 2019. – С. 75-86.
  4. Пирова А.Ю., Мееров И.Б., Козинов Е.А. Программный комплекс DMORSy для переупорядочения разреженных матриц на кластерных системах // Суперкомпьютерные дни в России: Труды международной конференции (24-25 сентября 2018 г., г. Москва). М.: Изд-во МГУ, 2018. – 1027 c. 2018. С. 749-757. 
  5. Пирова А.Ю., Кудрявцев Н.Ю., Мееров И.Б. Экспериментальное сравнение алгоритмов в параллельном многоуровневом методе вложенных сечений// Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2017. Т. 6, № 1. С. 38–55. DOI: 10.14529/cmse170103
  6. Pirova A., Meyerov I., Kozinov E., Lebedev S. PMORSy: parallel sparse matrix ordering software for fill-in minimization// Optimization Methods and Software. Vol. 32, No. 2. — 2017. — P. 274 -289. [preprint version]
  7. ЛебедевС.А., Мееров И.Б., Козинов Е.А., Ахмеджанов Д.Р., ПироваЮ., Сысоев А.В. Двухуровневый параллельный алгоритм выполнения численной фазы разложения Холецкого для разреженных матриц // Вестник УГАТУ. Т. 19, № 3(69). –Уфа, Изд-во УГАТУ, 2015. — C. 178–189.
  8. Lebedev S., Akhmedzhanov D., Kozinov E., Meyerov I., Pirova A., Sysoyev A. Dynamic Parallelization Strategies for Multifrontal Sparse Cholesky Factorization // Parallel Computing Technologies. – Springer International Publishing, 2015. – P. 68-79.
  9. Пирова A.Ю., Мееров И.Б., Козинов Е.А., Лебедев С.А. Параллельный алгоритм многоуровневого метода вложенных сечений для вычислительных систем с общей памятью// Вычислительные методы и программирование. Т. 16, № 3. — М.: Издательство НИВЦ МГУ, 2015. – С. 407–420.
  10. Pirova A., Meyerov I. MORSy – a new tool for sparse matrix reordering// An International Conference on Engineering and Applied Sciences Optimization. M. Papadrakakis, M.G. Karlaftis, N.D. Lagaros (eds.) (Kos Island, Greece, 4-6 June 2014). – pp. 1952-1963.
  11. Лебедев С.А., Мееров И.Б., Сысоев А.В., Бартенев Ю.Г., Бастраков С.И., Козинов Е.A., Лебедев И.Г., Пирова А.Ю., Стаканов А.Н. Оптимизация и применение пакета MUMPS для решения трехмерных стационарных задач прочности на кластерных системах// Вестник УГАТУ. Т. 18, № 3(64). –Уфа, Изд-во УГАТУ, 2014. — C. 276–282.
  12. Гергель В.П., Баркалов К.А., Мееров И.Б., Сысоев А.В., Бастраков С.И., Боголепов Д.К., Донченко Р.В., Козинов Е.А., Кустикова В.Д., Малова А. Ю., Сафонова Я.Ю., Сиднев А.А. Параллельные вычисления. Технологии и численные методы// Учебное пособие в 4-х томах. – Н. Новгород: изд-во ННГУ, 2013.

Конкурсы, проекты и гранты

  1. Стипендии Президента РФ назначены Пировой А.Ю. и Лебедеву С.А., приказ № 231 «О назначении стипендии Президента Российской Федерации молодым ученым и аспирантам, осуществляющим перспективные научные исследования и разработки по приоритетным направлениям модернизации российской экономики, на 2018-2020 годы» от  3.04.2018.
  2. Грант РФФИ № 14-01-31455 «Методы и высокопроизводительные программные средства для решения разреженных систем линейных уравнений с симметричной положительно определенной матрицей», 2014 г.
  3. ОКР с РФЯЦ-ВНИИЭФ «Разработка математических моделей и инструментальных средств для пакетов программ проектирования и имитационного моделирования на суперЭВМ». Результат выполнения проекта — оптимизация решателя MUMPSдля сокращения времени счета при решении задач с матрицами специального вида. 2012 г.

Дополнительная информация

MORSy — библиотека для переупорядочения разреженных матриц с целью минимизации заполнения