Geodesic
Sherman - Morrison high-performance algorithm for inverse matrix on GPU
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 3 (2014) no. 2, pp. 101-108 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: Sherman - Morrison formula, high-performance computing
Mots-clés : inverse matrix, sparse matrix. 
@article{VYURV_2014_3_2_a7,
     author = {N. S. Nedozhogin and A. S. Sarmakeeva and S. P. Kopysov},
     title = {Sherman - {Morrison} high-performance algorithm for inverse matrix on {GPU}},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {101--108},
     year = {2014},
     volume = {3},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2014_3_2_a7/}
}
TY  - JOUR
AU  - N. S. Nedozhogin
AU  - A. S. Sarmakeeva
AU  - S. P. Kopysov
TI  - Sherman - Morrison high-performance algorithm for inverse matrix on GPU
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2014
SP  - 101
EP  - 108
VL  - 3
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURV_2014_3_2_a7/
LA  - ru
ID  - VYURV_2014_3_2_a7
ER  - 
%0 Journal Article
%A N. S. Nedozhogin
%A A. S. Sarmakeeva
%A S. P. Kopysov
%T Sherman - Morrison high-performance algorithm for inverse matrix on GPU
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2014
%P 101-108
%V 3
%N 2
%U http://geodesic.mathdoc.fr/item/VYURV_2014_3_2_a7/
%G ru
%F VYURV_2014_3_2_a7
N. S. Nedozhogin; A. S. Sarmakeeva; S. P. Kopysov. Sherman - Morrison high-performance algorithm for inverse matrix on GPU. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 3 (2014) no. 2, pp. 101-108. http://geodesic.mathdoc.fr/item/VYURV_2014_3_2_a7/

[1] S.P. Kopysov, I.M. Kuzmin, N.S. Nedozhogin, A.K. Novikov, “Parallel Algorithms for Constructing and Solving the Schur Complement on Graphics Accelerators”, Physics and Mathematics, v. 154, Scientific Notes of Kazan University. Series “Physics and Mathematics”, no. 3, Publishing of Kazan University, Kazan, 2012, 202–215

[2] P. Ezzatti, E.S. Quintana-Orti, A. Remon, “Using Graphics Processors to Accelerate the Computation of the Matrix Inverse”, The Journal of Supercomputing, 58:3 (2011), 429–437 | DOI

[3] S.P.Kopysov, I.M. Kuzmin, N.S. Nedozhogin, A.K. Novikov, Y.A. Sagdeeva, “Hybrid Multi-GPU Solver Based on Schur Complement Method”, Parallel Computing Technologies, Lecture Notes in Computer Science, 7979, Springer, Heidelberg, 2013, 65–79 | DOI

[4] M. Woodbury, “Inverting Modified Matrices”, Memorandum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950

[5] J. Sherman, W.J. Morrison, “Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix”, The Annals of Mathematical Statistics, 21:1 (1950), 124–127 | DOI

[6] D.K. Faddeev, V.N. Faddeeva, Computational Methods of Linear Algebra, “Lan” Publishing, Saint-Petersburg, 2002, 736 pp.

[7] X. He, M. Holm, M. Neytcheva, “Parallel Implementation of the Sherman-Morrison Matrix Inverse Algorithm”, Applied Parallel and Scientific Computing, Lecture Notes in Computer Science, 7782, Springer, Heidelberg, 2013, 206–219 | DOI

[8] Matrix Market, (data obrascheniya: 29.08.2013) http://math.nist.gov/MatrixMarket/

[9] T. Davis, University of Florida Sparse Matrix Collection: Sparse Matrices from a Wide Range of Applications, (data obrascheniya: 29.08.2013) http://www.cise.ufl.edu/research/sparse/matrices/