Высокопроизводительный алгоритм Шермана-Моррисона обращения матриц на GPU

Никита Сергеевич Недожогин, Анастасия Семеновна Сармакеева, Сергей Петрович Копысов

Аннотация


Обращение матрицы является важным этапом при численном решении таких, задач как решение систем линейных уравнений и построение предобуславливателей, вычисление до-полнения Шура в методах декомпозиции области, цифровая обработка изображений и т. д. Разработка высопроизводительных параллельных алгоритмов обращения матриц связана с
эффективным хранением и отображением алгоритмов на современные многоядерные архи-тектуры. Наряду с традиционными методами обращения — LU -факторизацией и методом Гаусса – Жордана, рассмотрены параллельные алгоритмы метода сопряженных градиентов и Шермана – Моррисона, в которых используются матрично-векторные и скалярные произведения эффективно выполняемые на многоядерных процессорах. В работе проведено сравнение на тестовых матрицах рассматриваемых методов на CPU и GPU.

Ключевые слова


высокопроизводительные алгоритмы; обращение матриц; разреженные матрицы; алгоритм Шермана – Моррисона

Полный текст:

PDF

Литература


Копысов, С.П., Кузьмин, И.М., Недожогин, Н.С., Новиков, А.К. Параллельные алгоритмы формирования и решения системы дополнения Шура на графических ускорителях // Ученые записки Казанского университета. Серия Физ.-мат. науки – 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 MultiGPU 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)




DOI: http://dx.doi.org/10.14529/cmse140208