SHERMAN – MORRISON HIGH-PERFORMANCE ALGORITHM FOR INVERSE MATRIX ON GPU
DOI:
https://doi.org/10.14529/cmse140208Keywords:
Sherman – Morrison formula, high-performance computing, inverse matrix, sparse matrixAbstract
Matrix inversion is widely used in numerical methods, such as linear solvers, preconditioning
for linear system, domain decomposition, digital image processing, etc. High-performance
implementation of matrix inversion requires efficient matrix storage formats and optimal
distribution of computations between computing devices. In this paper, we study the performance
of traditional matrix inversion algorithms, such as LU-factorization and Gauss-Jordan, as well as
the conjugate gradient method and the Sherman – Morrison formula. In the last two algorithms,
matrix-vector products and scalar products are efficiently executed on multicore/manycore
processors. We compare the performance of the algorithms on hybrid multi-CPU multi-GPU
platforms, using the matrices from well-know test suites and from the numerical simulation of
wrap spring.
References
Копысов, С.П., Кузьмин, И.М., Недожогин, Н.С., Новиков, А.К. Параллельные алгоритмы формирования и решения системы дополнения Шура на графических ускорителях // Ученые записки Казанского университета. Серия Физ.-мат. науки – 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)
