Участник:NataliaPolienko/Блочное умножение матриц по методу Кеннона

Автор: Полиенко Н.А.

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

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

Одной из основных операций над матрицами является их перемножение. Данная операция широко применяется в большом количестве разных методов. Здесь мы рассмотрим умножение $C = AB$  квадратных матриц с помощью алгоритма Кеннона. Его суть заключается в том, что матрицы разбиваются на блоки, представляющие собой подматрицы исходных матриц. В следствии чего в качестве базовой подзадачи можно выбрать вычисления, связанные с определением одного из блоков результирующей матрицы $C$ .

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

Исходные данные: матрица $A$ размера $n \times n$, матрица $B$ размера $n \times n$.

Вычисляемые данные: матрица $C$ размера $n \times n$.

Исходные и результирующая матрицы представляются в виде наборов блоков. Операцию матричного умножения матриц $A$ и $B$ в блочном виде можно представить следующим образом : $\begin{bmatrix} A_{11} & A_{12} & \cdots & A_{1k} \\ A_{21} & A_{22} & \cdots & A_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ A_{k1} & A_{k2} & \cdots & A_{kk} \end{bmatrix} \begin{bmatrix} B_{11} & B_{12} & \cdots & B_{1k} \\ B_{21} & B_{22} & \cdots & B_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ B_{k1} & B_{k2} & \cdots & B_{kk} \end{bmatrix} = \begin{bmatrix} C_{11} & C_{12} & \cdots & C_{1k} \\ C_{21} & C_{22} & \cdots & C_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ C_{k1} & C_{k2} & \cdots & C_{kk} \end{bmatrix},$

где каждый блок $C_{ij}$ матрицы $C$ определяется в соответствии с выражением:

$\begin{align} C_{ij} = \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align}$

Полученные блоки $C_{ij}$ являются независимыми.

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

Вычислительное ядро перемножения матриц(квадратных) методом Кеннона можно составить из множественных вычислений умножения блоков матрицы $A$ на блоки матрицы $B$, таким образом получая блок результирующей матрицы $C$:

$\begin{align} C_{ij} = \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align}$

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

Как записано в описании ядра алгоритма, основную часть метода составляют множественные вычисления умножений блоков матрицы $A$ на блоки матрицы $B$:

$\begin{align} \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align}$

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

Алгоритм осуществляет последовательное вычисление блоков результирующей матрицы $C$: 1. Матрицы $A$, $B$ разбиваются на блоки фиксированного размера(будем предполагать, что блоки квадратные и порядок матрицы делится на размер блока без остатка). 2. На одной итерации цикла по переменной $i$ используется первая строка, состоящая из блоков матрицы $A$ и все столбцы, состоящие из блоков матрицы $B$: $\begin{align} C_{ij} = \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align}$

1.6 Последовательная сложность алгоритма

Для перемножения матриц размера $n \times n$ в последовательной реализации алгоритма требуется $n^3$ умножений и сложений.

1.8 Ресурс параллелизма алгоритма

Для алгоритма умножения квадратных матриц методом Кеннона размера $n \times n$ в параллельном варианте требуется последовательно выполнить следующие ярусы:

• по $m/k$ ярусов умножений и сложений (в каждом из ярусов — $(m/k)^2$ операций, где $m/k\lt math\gt - количество элементов в блоке). При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти. При классификации по высоте ЯПФ, таким образом, алгоритм умножения матриц относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''квадратичной'' (для квадратных матриц) или ''билинейной'' (для матриц общего вида). === Входные и выходные данные алгоритма === '''Входные данные''': матрица \lt math\gt A$, матрица $B$.

Объём входных данных: $n \times n + n \times n$

Выходные данные: матрица $C$ .

Объём выходных данных: $n \times n$