|
|
| Строка 1: |
Строка 1: |
| − | = Перемножение плотных неособенных матриц (последовательный вещественный вариант) =
| |
| | | | |
| − | == Свойства и структура алгоритма ==
| |
| − |
| |
| − | === Общее описание алгоритма ===
| |
| − |
| |
| − | '''Перемножение матриц''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
| |
| − | Здесь мы рассмотрим умножение <math>С = AВ</math> плотных неособенных матриц (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>.
| |
| − |
| |
| − | === Математическое описание алгоритма ===
| |
| − |
| |
| − | Исходные данные: плотная матрица <math>A</math> (элементы <math>a_{ij}</math>), плотная матрица <math>B</math> (элементы <math>b_{ij}</math>).
| |
| − |
| |
| − | Вычисляемые данные: плотная матрица <math>C</math> (элементы <math>c_{ij}</math>).
| |
| − |
| |
| − | Формулы метода:
| |
| − | :<math>
| |
| − | \begin{align}
| |
| − | c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad i \in [1, l].
| |
| − | \end{align}
| |
| − | </math>
| |
| − |
| |
| − | Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
| |
| − |
| |
| − | === Вычислительное ядро алгоритма ===
| |
| − |
| |
| − | Вычислительное ядро перемножения плотных неособенных матриц можно составить из множественных (всего их <math>l</math>) вычислений умножения матрицы <math>A</math> на столбцы матрицы <math>B</math>, или (при более детальном рассмотрении), из множественных (всего их <math>ml</math>) скалярных произведений строк матрицы <math>A</math> на столбцы матрицы <math>B</math>:
| |
| − |
| |
| − | :<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math>
| |
| − |
| |
| − | в режиме накопления или без него, в зависимости от требований задачи.
| |
| − |
| |
| − | === Макроструктура алгоритма ===
| |
| − |
| |
| − | Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные (всего <math>ml</math>) вычисления скалярных произведений строк матрицы <math>A</math> на столбцы матрицы <math>B</math>
| |
| − |
| |
| − | :<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math>
| |
| − |
| |
| − | в режиме накопления или без него.
| |
| − |
| |
| − | === Схема реализации последовательного алгоритма ===
| |
| − |
| |
| − | Для всех <math>i</math> от <math>1</math> до <math>m</math> и для всех <math>j</math> от <math>1</math> до <math>l</math> выполняются
| |
| − |
| |
| − | :<math>c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}</math>
| |
| − |
| |
| − | Особо отметим, что вычисления сумм вида <math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math> производят в режиме накопления прибавлением к текущему (временному) значению вычисляемого элемента матрицы <math>c_{ij}</math> произведений <math>a_{ik} b_{kj}</math> для <math>k</math> от <math>1</math> до <math>n</math>, '''c возрастанием''' <math>k</math>, вначале все элементы инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.
| |
| − |
| |
| − | === Последовательная сложность алгоритма ===
| |
| − |
| |
| − | Для умножения двух квадратных матриц порядка <math>n</math> (т.е. при <math>m=n=l</math>) в последовательном (наиболее быстром) варианте требуется:
| |
| − |
| |
| − | * по <math>n^3</math> умножений и сложений.
| |
| − |
| |
| − | Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на матрицу размером <math>m</math> строк на <math>n</math> столбцов в последовательном (наиболее быстром) варианте требуется:
| |
| − |
| |
| − | * по <math>mnl</math> умножений и сложений.
| |
| − |
| |
| − | При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матриц.
| |
| − |
| |
| − | При классификации по последовательной сложности, таким образом, алгоритм умножения матриц относится к алгоритмам ''с кубической сложностью'' (в случае неквадратных матриц - с ''трилинейной'').
| |
| − |
| |
| − | === Информационный граф ===
| |
| − |
| |
| − | Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.
| |
| − |
| |
| − | Граф алгоритма умножения плотных матриц состоит из одной группы вершин, расположенной в целочисленных узлах трёхмерной области, соответствующая ей операция <math>a+bc</math>.
| |
| − |
| |
| − | Естественно введённые координаты области таковы:
| |
| − | * <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
| |
| − | * <math>j</math> — меняется в диапазоне от <math>1</math> до <math>l</math>, принимая все целочисленные значения;
| |
| − | * <math>k</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.
| |
| − |
| |
| − | Аргументы операции следующие:
| |
| − | *<math>a</math>:
| |
| − | ** при <math>k = 1</math> константа <math>0</math>;
| |
| − | ** при <math>k > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j, k-1</math>;
| |
| − | *<math>b</math> — элемент ''входных данных'', а именно <math>a_{ik}</math>;
| |
| − | *<math>c</math> - элемент ''входных данных'' <math>b_{kj}</math>;
| |
| − |
| |
| − | Результат срабатывания операции является:
| |
| − | * при <math>k < n</math> - ''промежуточным данным'' алгоритма;
| |
| − | * при <math>k = n</math> - выходным данным <math>c_{ij}</math>.
| |
| − |
| |
| − | [[file:Dense mtrx product.png|thumb|center|800px|Рисунок 1. Умножение плотных матриц с отображением выходных данных]]
| |
| − |
| |
| − | === Ресурс параллелизма алгоритма ===
| |
| − |
| |
| − | Для алгоритма умножения квадратных матриц порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:
| |
| − |
| |
| − | * по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n^2</math> операций).
| |
| − |
| |
| − | Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на матрицу размером <math>n</math> строк на <math>l</math> столбцов в последовательном (наиболее быстром) варианте требуется:
| |
| − |
| |
| − | * по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>ml</math> операций).
| |
| − |
| |
| − | При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.
| |
| − |
| |
| − | При классификации по высоте ЯПФ, таким образом, алгоритм умножения матриц относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''квадратичной'' (для квадратных матриц) или ''билинейной'' (для матриц общего вида).
| |
| − |
| |
| − | === Входные и выходные данные алгоритма ===
| |
| − |
| |
| − | '''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), матрица <math>B</math> (элементы <math>b_{ij}</math>)).
| |
| − |
| |
| − | '''Объём входных данных''': <math>mn+nl</math>
| |
| − |
| |
| − | '''Выходные данные''': матрица <math>C</math> (элементы <math>c_{ij}</math>).
| |
| − |
| |
| − | '''Объём выходных данных''': <math>ml</math>
| |
| − |
| |
| − | === Свойства алгоритма ===
| |
| − |
| |
| − | Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''квадратичным'' или ''билинейным'' (отношение кубической или трилинейной к линейной).
| |
| − |
| |
| − | При этом вычислительная мощность алгоритма умножения матриц, как отношение числа операций к суммарному объему входных и выходных данных – ''линейно''.
| |
| − |
| |
| − | При этом алгоритм умножения матриц полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.
| |
| − |
| |
| − | == Литература ==
| |
| − | <references />
| |
