Geodesic
On use of assignment algorithms to reconstruct inverse matrices
Sibirskij žurnal industrialʹnoj matematiki, Tome 14 (2011) no. 2, pp. 63-68.

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

We consider the questions of reconstruction for the matrices inverse to the basis matrices of the revised simplex method. In order to choose the indices of pivots we use certain rules to form an auxiliary matrix from the basis matrix. The list of pivots results from solving assignment problems for the auxiliary matrix. On numerical examples of high dimension we analyze the efficiency of algorithms for solving assignment problems.
Keywords: revised simplex method, assignment problems.
Mots-clés : sparse matrices 
@article{SJIM_2011_14_2_a7,
     author = {G. I. Zabinyako},
     title = {On use of assignment algorithms to reconstruct inverse matrices},
     journal = {Sibirskij \v{z}urnal industrialʹnoj matematiki},
     pages = {63--68},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJIM_2011_14_2_a7/}
}
TY  - JOUR
AU  - G. I. Zabinyako
TI  - On use of assignment algorithms to reconstruct inverse matrices
JO  - Sibirskij žurnal industrialʹnoj matematiki
PY  - 2011
SP  - 63
EP  - 68
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJIM_2011_14_2_a7/
LA  - ru
ID  - SJIM_2011_14_2_a7
ER  - 
%0 Journal Article
%A G. I. Zabinyako
%T On use of assignment algorithms to reconstruct inverse matrices
%J Sibirskij žurnal industrialʹnoj matematiki
%D 2011
%P 63-68
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJIM_2011_14_2_a7/
%G ru
%F SJIM_2011_14_2_a7
G. I. Zabinyako. On use of assignment algorithms to reconstruct inverse matrices. Sibirskij žurnal industrialʹnoj matematiki, Tome 14 (2011) no. 2, pp. 63-68. http://geodesic.mathdoc.fr/item/SJIM_2011_14_2_a7/

[1] Bartels R. H., Golub G. H., “The simplex method of linear programming using LU decomposition”, Comm. ACM, 12:5 (1969), 266–268 | DOI | Zbl

[2] Forrest J. J. H., Tomlin J. A., “Updating tringular factors of the basic to maintain sparsity in the product-form simplex method”, Math. Programming, 2:3 (1972), 263–278 | DOI | MR | Zbl

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

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

[5] Burkard R. E., Derigs U., Assignment and matching problems: solution methods with FORTRAN-programs, Lecture Notes in Econ. and Math. Systems, 184, Springer, Berlin, 1980 | MR | Zbl

[6] Zabinyako G. I., “Perepostroenie obratnykh matrits”, Sib. zhurn. industr. matematiki, 12:3(39) (2009), 41–51 | MR

[7] 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

[8] Dijkstra E. W., “A note on two problems in connection with graphs”, Numer. Math., 1 (1959), 269–271 | DOI | MR | Zbl

[9] Dell'Amico M., Toth P., “Algorithms and codes for dense assignment problems: the state of the art”, Discrete Appl. Math., 100 (2000), 17–48 | DOI | MR

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

[11] Jonker R., Volgenant A., “A shortest augmenting path algorithm for dense and sparse linear assignment problems”, Computing, 38 (1987), 325–340 | DOI | MR | Zbl

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

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

[14] Jonker R., Vogenant A., Linear Assignment Problem http://www.assignmentproblems.com/LAPJV.htm