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

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