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

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

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

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

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

Коллектив

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

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

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

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

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

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

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

  1. Предложена модификация многоуровневой схемы метода вложенных сечений для переупорядочения разреженных матриц с целью уменьшения заполнения фактора. Разработанное ПО сопоставимо по качеству (размеру фактора) и скорости решения задач с широко распространенными реализациями METIS и Scotch. ПО доступно для скачивания и использования.
  2. Предложен способ распараллеливания мультифронтального метода для систем с общей памятью (численная фаза разложения Холецкого).
  3. Разработанное ПО интегрировано в программный комплекс «Виртуальное сердце», разрабатываемый на каф.ТУиДМ факультета ВМК ННГУ.
  4. Выполнена оптимизация решателя MUMPS для сокращения времени счета при решении задач с матрицами специального вида.

Текущие исследования

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

  • переупорядочение графа матрицы с целью уменьшения заполнения фактора;
  • символическая фаза разложения Холецкого;
  • численная фаза разложения Холецкого;
  • решение треугольных систем.

В 2014 году начаты работы по расширению области применения решателя на квадратные матрицы общего вида.

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

  1. Пирова А.Ю., Кудрявцев Н.Ю., Мееров И.Б. Экспериментальное сравнение алгоритмов в параллельном многоуровневом методе вложенных сечений // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2017. Т. 6, № 1. С. 38–55. DOI: 10.14529/cmse170103
  2. 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]
  3. Лебедев С.А., Мееров И.Б., Козинов Е.А., Ахмеджанов Д.Р., Пирова A.Ю., Сысоев А.В.  Двухуровневый параллельный алгоритм выполнения численной фазы разложения Холецкого для разреженных матриц // Вестник УГАТУ. Т. 19, № 3(69). –Уфа, Изд-во УГАТУ, 2015.  — C. 178–189.
  4. 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.
  5. Пирова A.Ю., Мееров И.Б., Козинов Е.А. , Лебедев С.А. Параллельный алгоритм многоуровневого метода вложенных сечений для вычислительных систем с общей памятью // Вычислительные методы и программирование. Т. 16, № 3. — М.: Издательство НИВЦ МГУ, 2015. – С. 407–420.
  6. Лебедев С.А., Мееров И.Б., Сысоев А.В., Бартенев Ю.Г., Бастраков С.И., Козинов Е.A., Лебедев И.Г., Пирова А.Ю., Стаканов А.Н. Оптимизация и применение пакета MUMPS для решения трехмерных стационарных задач прочности на кластерных системах // Вестник УГАТУ. Т. 18, № 3(64). –Уфа, Изд-во УГАТУ, 2014.  — C. 276–282.
  7. Гергель В.П., Баркалов К.А., Мееров И.Б., Сысоев А.В., Бастраков С.И., Боголепов Д.К., Донченко Р.В., Козинов Е.А., Кустикова В.Д., Малова А. Ю., Сафонова Я.Ю., Сиднев А.А. Параллельные вычисления. Технологии и численные методы // Учебное пособие в 4-х томах. – Н. Новгород: изд-во ННГУ, 2013.
  8. Bastrakov S. , Meyerov I., Gergel V., Gonoskov A., Gorshkov A., Efimenko E., Ivanchenko M., Kirillin M., Malova A., Osipov G.,  Petrov V., Surmin I., Vildemanov A. High performance computing in biomedical applications // Procedia Computer Science.  Volume 18. –Elsevier B.V., 2013. – Pp. 10–19.
  9. Козинов Е.А., Лебедев И.Г., Лебедев С.А., Мееров И.Б., Малова А.Ю., Сысоев А.В., Филиппенко С.C. Новый решатель для алгебраических систем разреженных линейных уравнений с симметричной положительно определенной матрицей // Вестник Нижегородского университета им. Н.И. Лобачевского. № 5(2).  – Н. Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2012. – C. 376-384.
  10. В.С. Петров, А.В. Вильдеманов, С.А. Григорьева, Е.А. Козинов, М.А. Комаров, В.А. Костин, А.К. Крюков, Т.А. Леванова, И.Б. Мееров, Г.В. Осипов. Программный комплекс «Виртуальное сердце» // Вестник Нижегородского университета им. Н.И. Лобачевского. № 5(2).  – Н. Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2012. – C. 438-447.

Избранные доклады

  1. Пирова А.Ю., Кудрявцев Н.Ю., Мееров И.Б. Экспериментальное сравнение алгоритмов в параллельном методе вложенных сечений // Параллельные вычислительные технологии – XI международная конференция, ПаВТ’2017, г. Казань, 3–7 апреля 2017 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2017. — С.  439-452.
  2. Лебедев С.А., Мееров И.Б., Козинов Е.А., Ахмеджанов Д.Р., Пирова A.Ю., Сысоев А.В. Двухуровневый параллельный алгоритм выполнения численной фазы разложения Холецкого для разреженных матриц // Суперкомпьютерные дни в России: труды международной конференции (Москва, 28-29 сентября 2015 г.) – С. 133-144.
  3. 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.
  4. Лебедев С.А., Козинов Е.А. Параллельный алгоритм выполнения численной фазы разложения Холецкого // Высокопроизводительные параллельные вычисления на кластерных сиcтемах: материалы XIV Международной конф.- г. Пермь, 10-12 ноября 2014 г.- Пермь: издательство ПНИПУ, 2014. — С. 262-268.
  5. Пирова А.Ю. Разработка переупорядочивателя симметричных разреженных матриц для систем с общей памятью // Высокопроизводительные параллельные вычисления на кластерных ситемах: материалы XIV Международной конф.- г. Пермь, 10-12 ноября 2014 г.- Пермь: издательство ПНИПУ, 2014. — С. 344-350.
  6. Ахмеджанов Д.Р., Лебедев С.А. Об одном подходе к реализации символьной фазы разложения Холецкого дря разреженных матриц // Высокопроизводительные параллельные вычисления на кластерных ситемах: материалы XIV Международной конф.- г. Пермь, 10-12 ноября 2014 г.- Пермь: издательство ПНИПУ, 2014. — С. 34-38.
  7. Пирова А.Ю. Разработка нового переупорядочивателя симметричных разреженных матриц // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы XIII Всероссийской конференции (Н. Новгород, 14–16 ноября2013 г.)–Нижний Новгород: изд-во ННГУ, 2013. – С. 211–215.
  8. Лебедев С.А., Козинов Е.А. Разработка нового решателя разреженных систем линейных уравнений // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы XIII Всероссийской конференции (Н. Новгород, 14–16 ноября2013 г.)–Нижний Новгород: изд-во ННГУ, 2013. – С. 301–306.
  9. Лебедев С.А., Мееров И.Б., Сысоев А.В., Бартенев Ю.Г., Бастраков С.И., Козинов Е.А., Лебедев И.Г., Малова А.Ю., Старостин Н.В., Стаканов А.Н. Оптимизация и применение пакета MUMPS для решения трехмерных стационарных задач прочности на кластерных системах // Научный сервис в сети Интернет: все грани параллелизма: Труды Международной суперкомпьютерной конференции (23-28 сентября 2013 г., г. Новороссийск).–М.: Изд-во МГУ, 2013. –С. 233–237.
  10. Козинов Е.А., Лебедев И.Г., Лебедев С.А., Линев А.В., Малова А.Ю., Мееров И.Б., Сысоев А.В., Сысоева Т.А., Филиппенко С.C. Разработка прямого решателя для разреженных систем линейных уравнений с симметричной положительно определенной матрицей // Параллельные вычислительные технологии (ПаВТ’2012): труды международной научной конференции (Новосибирск, 26 – 30 марта 2012 г.) – Челябинск: Издательский центр ЮУрГУ, 2012. – С. 525–530.
  11. Малова А. Ю. Обзор методов переупорядочения разреженных матриц // 12-я всероссийская конференция «Высокопроизводительные параллельные вычисления на кластерных системах (HPC-2012)» (Нижний Новгород, 26 – 28 ноября 2012 г.). – Нижний Новгород: изд-во ННГУ, 2012. – С. 257–264.
  12. Козинов Е.А., Лебедев И.Г., Лебедев С.А., Линев А.В., Малова А.Ю., Мееров И.Б., Сысоев А.В., Сысоева Т.А., Филиппенко С.C., Гергель В.П. Разработка прямого решателя для разреженных систем линейных уравнений с симметричной положительно определенной матрицей // 11-я Международная конференция «Высокопроизводительные вычисления на кластерных системах (HPC-2011)» (31 октября – 3 ноября 2011 г., г. Нижний Новгород). – Нижний Новгород: изд-во ННГУ, 2011. – С. 163–167.

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

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

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

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