Высокопроизводительный алгоритм Шермана - Моррисона обращения матриц на GPU
Автор: Недожогин Никита Сергеевич, Сармакеева Анастасия Семеновна, Копысов Сергей Петрович
Рубрика: Краткие сообщения
Статья в выпуске: 2 т.3, 2014 года.
Бесплатный доступ
Обращение матрицы является важным этапом при численном решении таких, задач как решение систем линейных уравнений и построение предобуславливателей, вычисление дополнения Шура в методах декомпозиции области, цифровая обработка изображений и т. д. Разработка высокопроизводительных параллельных алгоритмов обращения матриц связана с эффективным хранением и отображением алгоритмов на современные многоядерные архитектуры. Наряду с традиционными методами обращения - LU-факторизацией и методом Гаусса - Жордана, рассмотрены параллельные алгоритмы метода сопряженных градиентов и Шермана - Моррисона, в которых используются матрично-векторные и скалярные произведения эффективно выполняемые на многоядерных процессорах. В работе проведено сравнение на тестовых матрицах рассматриваемых методов на CPU и GPU.
Высокопроизводительные алгоритмы, обращение матриц, разреженные матрицы, алгоритм шермана - моррисона
Короткий адрес: https://sciup.org/147160526
IDR: 147160526
Список литературы Высокопроизводительный алгоритм Шермана - Моррисона обращения матриц на GPU
- Копысов, С.П., Кузьмин, И.М., Недожогин, Н.С., Новиков, А.К. Параллельные алгоритмы формирования и решения системы дополнения Шура на графических ускорителях//Ученые записки Казанского университета. Серия Физ.-мат. науки -2012. -Т. 154. №3. -С. 202-215.
- Ezzatti, P., Quintana-Orti, E.S., Remon, A. Using graphics processors to accelerate the computation of the matrix inverse//J. of Supercomputing. -2011. V.58. -P.429-437.
- Kopysov, S.P., Kuzmin, I.M., Nedozhogin, N. S., Novikov, A.K., Sagdeeva, Y.A. Hybrid Multi-GPU solver based on Schur complement method//Lecture Notes in Computer Science -2013. -vol. 7979. -pp. 65-79.
- Woodbury, M. Inverting modified matrices//Memorandum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950.
- Sherman, J., Morrison, W.J. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix//Ann. Math. Statistics. -1950. -V. 21. №1. -P. 124-127.
- Фаддеев, Д.К., Фаддеева, В.Н. Вычислительные методы линейной алгебры. -СПб.: Издво "Лань 2002. -736 с.
- He, X., Holm, M., Neytcheva, M. Efficiently parallel implementation of the inverse Sherman -Morrison algorithm//Lecture Notes in Computer Science. -2013. -V. 7782. -P. 206-219.
- Matrix Market: URL: http://math.nist.gov/MatrixMarket/(дата обращения: 29.08.2013)
- Davis, T. University of Florida Sparse Matrix Collection: sparse matrices from a wide range of applications: URL: http://www.cise.ufl.edu/research/sparse/matrices/(дата обращения: 29.08.2013)
