Применение теории графов в алгебраических многосеточных методах для решения разреженных СЛАУ
Автор: Герб Артем Родионович, Омарова Гульзира Алимовна
Журнал: Проблемы информатики @problem-info
Рубрика: Параллельное системное программирование и вычислительные технологии
Статья в выпуске: 3 (56), 2022 года.
Бесплатный доступ
В работе рассматриваются геометрические и алгебраические многосеточные методы, алгоритмы огрубения графов, метрики, которые используются для построения агрегаций вершин. Реализован метод огрубления на основе метрики А. Напова и И. Нотея. Для оптимизации времени вычислений используются алгоритмы Густавсона для эффективного умножения и транспонирования матриц формата CSR, что позволило обрабатывать графы с количеством вершин более миллиона. Целью представленной работы является разработка структуры данных и компонент вычислительного окружения для высокопроизводительного решения широкого класса СЛАУ.
Огрубление графа, граф сетка, метрика, разреженные матрицы, структуры данных
Короткий адрес: https://sciup.org/143179395
IDR: 143179395 | УДК: 519.17-519.61 | DOI: 10.24412/2073-0667-2022-3-77-89
Application of graph theory in algebraic multigrid methods for solving sparse SLAES
In this paper, we discuss geometric and algebraic multigrid methods, graph coarsening algorithms, and metrics used to construct vertex aggregations. A coarsening method based on A. Napov and Y. Notey’s criterion is implemented. Gustavson’s algorithms for efficient multiplication and transposition of matrices in CSR format are used for computation time optimization, which allowed to process graphs with more than one million vertices. The purpose of the presented work is to develop a data structure and computational environment components for high-performance solution of a wide class of SLAEs.
Список литературы Применение теории графов в алгебраических многосеточных методах для решения разреженных СЛАУ
- Kron G. Tensor Analysis of Networks // Wiley, NewYork. 1939.
- Chen J., Saad Y., Zhang Z.. Graph coarsening: from scientific computing to machine learning// SeMA Journal. 2022.
- Федоренко P. П. Релаксационный метод решения разностных эллиптических уравнений // Ж. вычисл. матем. и матем. физ. 1961.
- Федоренко Р. П. О скорости сходимости одного итерационного процесса // Ж. вычисл. матем. и матем. физ. 1964.
- Hackbusch W. Multigrid Methods and Applications // Springer-Verlag, Berlin, Germany, 1985.
- Pennanen, Anssi. A graph-based multigrid with applications// University of Jyvascyla. 2010.
- Ruge J. W. and Staben K. Algebraic Multigrid (AMG)// In S.F. McCornick, editor, Multigrid Methods, Frontiers in Applied Mathematics, SIAM, Philadelphia, Pennsylvania. 1987.
- Napov A. and Notay Y. An efficient multigrid method for Laplacian systems// Kent State University. 2016.
- Napov A. and Notay Y. An efficient multigrid method for Laplacian systems II: robust aggregation// Society for Industrial and Applied Mathematics. 2016.
- Nagele S., Falgout R. D., and Wittum G. Filtering algebraic multigrid and adaptive strategies// Computing and Visualization in Science. 2008.
- Notay Y. An aggregation-based algebraic multigrid method// Electron. Trans. Numer. Anal. 2010.
- Napov A. and Notay Y. An algebraic multigrid method with guaranteed convergence rate// SIAM J. Sci. Comput. 2012.
- Beck R. Graph-based algebraic multigrid for Lagrange-type finite elements on simplicial meshes // Preprint SC 99-22, Konrad-Zuse-Zentrum fur Informa-tionstechnik, Berlin, 1999.
- Braess D. Towards algebraic multigrid for elliptic problems of second order // Computing. 1995.
- Elman EL C., Silvester D. J., and Wathen A. J. Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics // Oxford University Press, 2005.
- Livne О. E. and Brandt A. Lean algebraic multigrid (LAMG): fast graph laplacian linear solver// SIAM J. Sci. Comput. 2012.
- Dorfler, F., Bullo, F. Kron reduction of graphs with applications to electrical networks // IEEE Trans. Circuits Syst. I Reg. Pap. 60. 2013.
- Shuman, D.L, Faraji, M.J., Vandergheynst, P. A multiscale pyramid transform for graph signals// IEEE Trans. Signal Process. 2016.
- Aspvall, B., Gilbert, J.R. Graph coloring using eigenvalue decomposition // SIAM J. Algebr. Discrete Methods. 1984.
- Spielman, D.A., Srivastava, N. Graph sparsification by effective resistances /7 SIAM J. Comput. 2011.
- Писанецки С. Технология разреженных матриц // Мир. 1988.
- Ruge J. W. and Staben K. Algebraic multigrid, in Multigrid Methods, Frontiers Appl // Math. 3, S. F. McCormick, cd., SIAM, Philadelphia. 1987.
- Ron D., Safro I., and A. Brandt A. Relaxation-based coarsening and multiscalc graph organization, Multiscale Model// Simul. 2011.
