Применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений

Аннотация

Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье продемонстрировано применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений. Концепция Q-детерминанта основана на унифицированном представлении численных алгоритмов в форме Q-детерминанта. Любой численный алгоритм имеет Q-детерминант. Q-детерминант состоит из Q-термов. Их число равно числу выходных данных алгоритма. Каждый Q-терм описывает все возможные способы вычисления одного из выходных данных на основе входных данных. Q-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции Q-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции Q-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется Q-эффективной. В качестве применения метода проектирования Q-эффективных программ описано проектирование программ для реализации метода сопряженных градиентов на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ».