Высокопроизводительный алгоритм Шермана-Моррисона обращения матриц на 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