Using massively parallel computations for absolutely precise solution of the linear programming problems

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 ⁴ + O(lm ³), 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.