Перемножение плотных неособенных матриц (последовательный вещественный вариант)

Основные авторы описания: А.В.Фролов.

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

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

Перемножение матриц - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов. Здесь мы рассмотрим умножение [math]\displaystyle{ C = AB }[/math]  плотных неособенных матриц (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения.

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

Исходные данные: плотная матрица [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{ \begin{align} c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad j \in [1, l]. \end{align} }[/math]

Существует также блочная версия метода, однако в данном описании разобран только точечный метод.

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

Вычислительное ядро перемножения плотных неособенных матриц можно составить из множественных (всего их [math]\displaystyle{ l }[/math]) вычислений умножения матрицы [math]\displaystyle{ A }[/math] на столбцы матрицы [math]\displaystyle{ B }[/math], или (при более детальном рассмотрении), из множественных (всего их [math]\displaystyle{ ml }[/math]) скалярных произведений строк матрицы [math]\displaystyle{ A }[/math] на столбцы матрицы [math]\displaystyle{ B }[/math]:

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

в режиме накопления или без него, в зависимости от требований задачи.

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

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

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

в режиме накопления или без него.

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

Для всех [math]\displaystyle{ i }[/math] от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ m }[/math] и для всех [math]\displaystyle{ j }[/math] от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ l }[/math] выполняются

[math]\displaystyle{ c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj} }[/math]

Особо отметим, что вычисления сумм вида [math]\displaystyle{ \sum_{k = 1}^{n} a_{ik} b_{kj} }[/math] производят в режиме накопления прибавлением к текущему (временному) значению вычисляемого элемента матрицы [math]\displaystyle{ c_{ij} }[/math] произведений [math]\displaystyle{ a_{ik} b_{kj} }[/math] для [math]\displaystyle{ k }[/math] от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math], c возрастанием [math]\displaystyle{ k }[/math], вначале все элементы инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.

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

Для умножения двух квадратных матриц порядка [math]\displaystyle{ n }[/math] (т.е. при [math]\displaystyle{ m=n=l }[/math]) в последовательном (наиболее быстром) варианте требуется:

• по [math]\displaystyle{ n^3 }[/math] умножений и сложений.

Для умножения матрицы размером [math]\displaystyle{ m }[/math] строк на [math]\displaystyle{ n }[/math] столбцов на матрицу размером [math]\displaystyle{ n }[/math] строк на [math]\displaystyle{ l }[/math] столбцов в последовательном (наиболее быстром) варианте требуется:

• по [math]\displaystyle{ mnl }[/math] умножений и сложений.

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матриц.

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

Информационный граф

Опишем граф алгоритма как аналитически, так и в виде рисунка.

Граф алгоритма умножения плотных матриц состоит из одной группы вершин, расположенной в целочисленных узлах трёхмерной области, соответствующая ей операция [math]\displaystyle{ a+bc }[/math].

Естественно введённые координаты области таковы:

• [math]\displaystyle{ i }[/math] — меняется в диапазоне от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ m }[/math], принимая все целочисленные значения;
• [math]\displaystyle{ j }[/math] — меняется в диапазоне от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ l }[/math], принимая все целочисленные значения;
• [math]\displaystyle{ k }[/math] — меняется в диапазоне от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math], принимая все целочисленные значения.

Аргументы операции следующие:

• [math]\displaystyle{ a }[/math]:
  • при [math]\displaystyle{ k = 1 }[/math] константа [math]\displaystyle{ 0 }[/math];
  • при [math]\displaystyle{ k \gt 1 }[/math] — результат срабатывания операции, соответствующей вершине с координатами [math]\displaystyle{ i, j, k-1 }[/math];
• [math]\displaystyle{ b }[/math] — элемент входных данных, а именно [math]\displaystyle{ a_{ik} }[/math];
• [math]\displaystyle{ c }[/math] - элемент входных данных [math]\displaystyle{ b_{kj} }[/math];

Результат срабатывания операции является:

• при [math]\displaystyle{ k \lt n }[/math] - промежуточным данным алгоритма;
• при [math]\displaystyle{ k = n }[/math] - выходным данным [math]\displaystyle{ c_{ij} }[/math].

Рисунок 1. Умножение плотных матриц с отображением выходных данных

Интерактивное изображение графа алгоритма без входных и выходных данных для случая перемножения двух квадратных матриц порядка 3 и 4

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

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

• по [math]\displaystyle{ n }[/math] ярусов умножений и сложений (в каждом из ярусов — [math]\displaystyle{ n^2 }[/math] операций).

Для умножения матрицы размером [math]\displaystyle{ m }[/math] строк на [math]\displaystyle{ n }[/math] столбцов на матрицу размером [math]\displaystyle{ n }[/math] строк на [math]\displaystyle{ l }[/math] столбцов в последовательном (наиболее быстром) варианте требуется:

• по [math]\displaystyle{ n }[/math] ярусов умножений и сложений (в каждом из ярусов — [math]\displaystyle{ ml }[/math] операций).

При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

Входные и выходные данные алгоритма

Входные данные: матрица [math]\displaystyle{ A }[/math] (элементы [math]\displaystyle{ a_{ij} }[/math]), матрица [math]\displaystyle{ B }[/math] (элементы [math]\displaystyle{ b_{ij} }[/math])).

Объём входных данных: [math]\displaystyle{ mn+nl }[/math]

Выходные данные: матрица [math]\displaystyle{ C }[/math] (элементы [math]\displaystyle{ c_{ij} }[/math]).

Объём выходных данных: [math]\displaystyle{ ml }[/math]

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является квадратичным или билинейным (отношение кубической или трилинейной к линейной).

При этом вычислительная мощность алгоритма умножения матриц, как отношение числа операций к суммарному объему входных и выходных данных – линейно.

При этом алгоритм умножения матриц полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

Программная реализация алгоритма

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

В простейшем варианте алгоритм умножения матриц на Фортране можно записать так:

         
	DO  I = 1, M
        DO  J = 1, L
		S = 0.
		DO  K = 1, N
			S = S + DPROD(A(I,K), B(K,J))
		END DO	
	        C(I, J) = S
        END DO
	END DO

При этом для реализации режима накопления переменная [math]\displaystyle{ S }[/math] должна быть двойной точности.