Применение массивно-параллельных вычислений для решения задач линейного программирования с абсолютной точностью

Рассмотрены подходы к решению задачи линейного программирования с абсолютной точностью, достигаемой применением дробно-рациональных вычислений без округления в алгоритмах симплекс-метода. Показано, что меньшую пространственную сложность имеет реализация модифицированного симплекс-метода с использованием обратной матрицы. Объем оперативной памяти, достаточный для решения задачи линейного программирования с использованием дробно-рациональных вычислений без округления, не превосходит величины $4lm^4+O(lm^3)$, где $m$ – минимальная из размерностей задачи, $l$ – число бит, достаточных для представления одного элемента матрицы исходных данных. Показано,что эффективность распараллеливания (т.е. отношение ускорения к числу процессоров) составляет в асимптотике величину, близкую к 100 %. Результаты вычислительного эксперимента практических задач с разреженной матрицей подтверждают высокую эффективность распараллеливания и демонстрируют преимущество параллельного метода обратной матрицы.

Статья представлена к публикации членом редколлегии: А. И. Кибзун