Geodesic
Re-Construction of Inverse Matrices
Sibirskij žurnal industrialʹnoj matematiki, Tome 12 (2009) no. 3, pp. 41-51.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider algorithms for re-constructing the inverses to basis matrices, in which the advance determination of the pivots is based on solving assignment problems. Then, in order to memory saving, by symmetric permutations, we set the order in which the pivots are used. The corresponding routines are designed for the software packages for solving mathematical programming problems.
Keywords: linear programming, systems of linear algebraic equations, assignment problem.
Mots-clés : sparse matrices 
@article{SJIM_2009_12_3_a4,
     author = {G. I. Zabinyako},
     title = {Re-Construction of {Inverse} {Matrices}},
     journal = {Sibirskij \v{z}urnal industrialʹnoj matematiki},
     pages = {41--51},
     publisher = {mathdoc},
     volume = {12},
     number = {3},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJIM_2009_12_3_a4/}
}
TY  - JOUR
AU  - G. I. Zabinyako
TI  - Re-Construction of Inverse Matrices
JO  - Sibirskij žurnal industrialʹnoj matematiki
PY  - 2009
SP  - 41
EP  - 51
VL  - 12
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJIM_2009_12_3_a4/
LA  - ru
ID  - SJIM_2009_12_3_a4
ER  - 
%0 Journal Article
%A G. I. Zabinyako
%T Re-Construction of Inverse Matrices
%J Sibirskij žurnal industrialʹnoj matematiki
%D 2009
%P 41-51
%V 12
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJIM_2009_12_3_a4/
%G ru
%F SJIM_2009_12_3_a4
G. I. Zabinyako. Re-Construction of Inverse Matrices. Sibirskij žurnal industrialʹnoj matematiki, Tome 12 (2009) no. 3, pp. 41-51. http://geodesic.mathdoc.fr/item/SJIM_2009_12_3_a4/

[1] Murtaf B., Sovremennoe lineinoe programmirovanie. Teoriya i praktika, Mir, M., 1984 | MR

[2] Markowitz H. M., “The elimination form of the inverse and its applications to linear programming”, Management Sci., 3 (1957), 255–269 | DOI | MR | Zbl

[3] Pissanetski S., Tekhnologiya razrezhennykh matrits, Mir, M., 1988 | MR

[4] Esterbyu O., Zlatev Z., Pryamye metody dlya razrezhennykh matrits, Mir, M., 1987 | MR

[5] Li X., Direct solvers for sparse matrices, http://crd.lbl.gov/~xiaoye/SuperLU/SparseDirectSurvey.pdf

[6] Hellerman E., Rarick D. C., “Reinversion with the preassigned pivot procedure”, Math. Prog., 1 (1971), 195–216 | DOI | MR | Zbl

[7] Hellerman E., Rarick D. C., “The partitioned preassigned pivot procedure ($P^4$)”, Sparse Matrices and Their Applications, Plenum Press, New York, 1972, 68–76 | MR

[8] Erisman A. M., Grimes R. G., Lewis J. G., Poole W. G. (Jr.), “A structurally stable modification of Hellerman–Rarick's $P^4$ algorithm for reordering unsymmetric sparse matrices”, SIAM J. Numer. Anal., 22:2 (1985), 369–385 | DOI | MR | Zbl

[9] Erisman A. M., Grimes R. G., Lewis J. G., PooleW. G., Simon H. D., “Evalution of reorderings unsymmetric sparse matrices”, SIAM J. Sci. Stat. Comput., 8:4 (1987), 601–624 | MR

[10] Olschowka M., Neumaier A., “A new pivoting strategy for Gaussian elimination”, Linear Algebra Appl., 240:1–3 (1996), 131–151 | DOI | MR

[11] Duff I. S., Koster J., “The design and use of algorithms for permuting large entries to the diagonal of sparse matrices”, SIAM J. Matrix Anal. Appl., 20:4 (1999), 889–901 | DOI | MR | Zbl

[12] Li X. C., Demmel W., “A scalable sparse direck solver using static pivoting”, Proc. 9 SIAM Conf. on Parallel Processing for Scientific Computing, San Antonio, 1999, 10 | MR

[13] Schenk O., Gartner K., “Solving unsymmetric sparse systems of linear equation with PARDISO”, Future Generation Computer Systems, 20 (2004), 475–487 | DOI

[14] Carpaneto G., Toth P., “Solution of the assignment problem (Algorithm 548)”, ACM Trans. Math. Software, 6:1 (1980), 104–111 | DOI

[15] Burkard R. E., Derigs U., Assignment and Matching Problems: SolutionMethods with FORTRAN-Programs, Lecture Notes in Econ. and Math. Systems, 184, 1980 | MR | Zbl

[16] Karypis G., Kumar V., METIS. A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices (Version 4.0), http:// www.cs.umn.edu/~karypis

[17] Karypis G., Kumar V., “A fast and high quality multivel scheme for partitioning irregular graphs”, SIAM J. Sci. Computing, 20:1 (1998), 359–392 | DOI | MR

[18] Brayton R. K., Gustavson F. G., Willoghby R. A., “Some results on sparse matrices”, Math. Comput., 24:112 (1970), 937–954 | DOI | MR

[19] Davis T. A., University of Florida sparse matrix collection, http://www.cise.ufl.edu/~davis/sparse

[20] Matrix Market, http://math.nist.gov/MatrixMarket

[21] Forsait Dzh., Malkolm M., Mouler K., Mashinnye metody matematicheskikh vychislenii, Mir, M., 1980 | MR