Приложение 9: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(Полностью удалено содержимое страницы)
Строка 1: Строка 1:
 +
= Перемножение плотных неособенных матриц (последовательный вещественный вариант) =
  
 +
== Свойства и структура алгоритма ==
 +
 +
=== Общее описание алгоритма ===
 +
 +
'''Перемножение матриц''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
 +
Здесь мы рассмотрим умножение <math>С = AВ</math>&nbsp; плотных неособенных матриц (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения<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 />

Версия 11:18, 17 сентября 2015

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

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

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

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

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

Исходные данные: плотная матрица [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]

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

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

Вычислительное ядро перемножения плотных неособенных матриц можно составить из множественных (всего их [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]

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

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

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

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

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

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

Для всех [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], вначале все элементы инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.

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

Для умножения двух квадратных матриц порядка [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 в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матриц.

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

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

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

Граф алгоритма умножения плотных матриц состоит из одной группы вершин, расположенной в целочисленных узлах трёхмерной области, соответствующая ей операция [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 \gt 1[/math] — результат срабатывания операции, соответствующей вершине с координатами [math]i, j, k-1[/math];
  • [math]b[/math] — элемент входных данных, а именно [math]a_{ik}[/math];
  • [math]c[/math] - элемент входных данных [math]b_{kj}[/math];

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

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

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

Для алгоритма умножения квадратных матриц порядка 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] операций).

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

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

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

Входные данные: матрица [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]

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

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

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

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

1.2 Литература

  1. ↑ В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
Источник — https://algowiki-project.org/w/ru/index.php?title=Приложение_9&oldid=2551