Применение теории графов в алгебраических многосеточных методах для решения разреженных СЛАУ
Автор: Герб Артем Родионович, Омарова Гульзира Алимовна
Журнал: Проблемы информатики @problem-info
Рубрика: Параллельное системное программирование и вычислительные технологии
Статья в выпуске: 3 (56), 2022 года.
Бесплатный доступ
В работе рассматриваются геометрические и алгебраические многосеточные методы, алгоритмы огрубения графов, метрики, которые используются для построения агрегаций вершин. Реализован метод огрубления на основе метрики А. Напова и И. Нотея. Для оптимизации времени вычислений используются алгоритмы Густавсона для эффективного умножения и транспонирования матриц формата CSR, что позволило обрабатывать графы с количеством вершин более миллиона. Целью представленной работы является разработка структуры данных и компонент вычислительного окружения для высокопроизводительного решения широкого класса СЛАУ.
Огрубление графа, граф сетка, метрика, разреженные матрицы, структуры данных
Короткий адрес: https://sciup.org/143179395
IDR: 143179395 | DOI: 10.24412/2073-0667-2022-3-77-89
Список литературы Применение теории графов в алгебраических многосеточных методах для решения разреженных СЛАУ
- 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.
