Open AccessA parallel multilevel nested dissection algorithm for shared-memory computing systems
Author(s) -
Anna Pirova,
И. Б. Мееров,
Evgeny Kozinov,
С. А. Лебедев
Publication year - 2015
Publication title -
vyčislitelʹnye metody i programmirovanie
Language(s) - English
Resource type - Journals
eISSN - 1726-3522
pISSN - 0507-5386
DOI - 10.26089/nummet.v16r339
Subject(s) - cholesky decomposition , computer science , minimum degree algorithm , parallel computing , shared memory , supercomputer , sparse matrix , parallel algorithm , distributed memory , algorithm , load balancing (electrical power) , matrix (chemical analysis) , incomplete cholesky factorization , mathematics , grid , eigenvalues and eigenvectors , physics , geometry , materials science , quantum mechanics , composite material , gaussian
Рассматривается задача переупорядочения строк и столбцов симметричной положительно определенной разреженной матрицы с целью уменьшения числа ненулевых элементов в факторе Холецкого. Данная задача является NP-полной. Для ее решения используются эвристические алгоритмы, основанные на примененииметодов теории графов. Предлагается параллельный алгоритм переупорядочения для вычислительных систем с общей памятью. В качестве базы для распараллеливания используется модификация многоуровневого метода вложенных сечений, ранее реализованная авторами в виде библиотеки с открытым исходным кодом MORSy.Основная идея распараллеливания заключается в организации и параллельной обработке очереди задач,которые могут быть решены независимо. В отличие от широко распространенных аналогов, применяющих MPI для организации параллелизма как на распределенной, так и на общей памяти, предложенный алгоритм использует возможности стандарта OpenMP 3.0. Вычислительные эксперименты выполнены на симметричных положительно определенных матрицах из коллекции университета Флориды. Показано, что параллельный код MORSy дает сходные или лучшие перестановки в сравнении с библиотекой ParMETIS для всех тестовых матриц, кроме одной, в большинстве случаев опережая ParMETIS по времени работы. Программная реализация выполнена в виде библиотеки с открытым исходным кодом и доступна для скачивания на сайте Приволжского научно-образовательного центра суперкомпьютерных технологий. This paper deals with the NP-complete problem of finding a symmetric positive definite sparse matrix ordering that minimizes the Cholesky factor fill-in. For this purpose, heuristic approaches based on graph algorithms are applied. A new parallel ordering algorithm for shared-memory computing systems is proposed. The modified multilevel nested dissection algorithm from the recently presented MORSy library is used as a basis for ordering. The parallel processing is done in a task-based fashion. It uses the OpenMP 3.0 task parallelism relying on the dynamic load balancing implemented during the OpenMP runtime. The numerical experiments were performed using a number of symmetric positive definite matrices from the University of Florida Sparse Matrix Collection. The experimental results show the competitiveness of the proposed implementation on shared memory systems compared to the widely used ParMETIS library. In our experiments, the parallel MORSy version provides a better ordering than ParMETIS on all but one matrix in terms of the Cholesky factor fill-in and outperforms ParMETIS in most cases. The parallel MORSy version is publicly available from the Supercomputing Centerof Lobachevsky State University of Nizhni Novgorod.