Алгоритм Фокса умножения матриц

Свойства и структура алгоритмов

Общее описание алгоритма

Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.

Математическое описание алгоритма

Исходные данные: квадратная матрица [math]\displaystyle{ A }[/math] (состоит из блоков [math]\displaystyle{ A_{ij} }[/math]), квадратная матрица [math]\displaystyle{ B }[/math] (состоит из блоков [math]\displaystyle{ B_{ij} }[/math]).

Вычисляемые данные: квадратная матрица [math]\displaystyle{ C }[/math] (состоит из блоков [math]\displaystyle{ C_{ij} }[/math]).

При этом каждый блок [math]\displaystyle{ C_{ij} }[/math] определяется как произведение соответствующих блоков матриц [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] :

[math]\displaystyle{ \begin{align} C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1]. \end{align} }[/math]

Вычислительное ядро алгоритма

Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы [math]\displaystyle{ A }[/math] на блоки матрицы [math]\displaystyle{ B }[/math]

[math]\displaystyle{ \begin{align} \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1]. \end{align} }[/math]

Макроструктура алгоритма

Как уже записано в описании ядра алгоритма, основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы [math]\displaystyle{ A }[/math] на блоки матрицы [math]\displaystyle{ B }[/math]. Перемножать блоки будем стандартным методом, используя определение произведения матриц:

[math]\displaystyle{ \begin{align} \sum_{k = 1}^{n} a_{ik} b_{kj} \end{align} }[/math]

Схема реализации последовательного алгоритма

Разобьем исходные матрицы на блоки [math]\displaystyle{ A_{ij} }[/math],[math]\displaystyle{ B_{ij} }[/math] и [math]\displaystyle{ C_{ij} }[/math] соответственно. Обнулим блоки матрицы [math]\displaystyle{ C }[/math], предназначенной для хранения соответствующего результирующего произведения [math]\displaystyle{ AB }[/math]. Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

[math]\displaystyle{ \begin{align} С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1]. \end{align} }[/math]

После завершения цикла мы получим матрицу с блоками [math]\displaystyle{ C_{ij} }[/math], соответствующую произведению [math]\displaystyle{ AB }[/math].