Abstract:
Consideration was given to the approaches to solve the linear programming problems with an absolute precision attained through rational computation without roundoff in the algorithms of the simplex method. Realization of the modified simplex method with the use of the inverse matrix was shown to have the least spatial complexity. The main memory area sufficient to solve the linear programming problem with the use of rational computations without roundoff is at most $4lm^4+O(lm^3)$, where $m$ is the minimal problem size and $l$ is the number of bits sufficient to represent one element of the source data matrix. The efficiency of parallelization, that is, the ratio of acceleration to the number of processors, was shown to be asymptotically close to 100 %. Computing experiments on practical problems with the sparse matrix corroborated high efficiency of parallelization and demonstrated the advantage of the parallel method of inverse matrix.
Presented by the member of Editorial Board:A. I. Kibzun
Fulltext:
PDF file (291 kB)
