Difference between revisions of "Dense matrix multiplication (serial version for real matrices)"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][quality revision]
Line 1: Line 1:
−
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|2.4]])
+
Primary authors of this description: [[:ru:Участник:Frolov|A.V.Frolov]], [[:ru:Участник:VadimVV|Vad.V.Voevodin]] ([[#Locality of data and computations|Section 2.2]]), [[:ru:Участник:Teplov|A.M.Teplov]] (раздел [[#Scalability of the algorithm and its implementations|Section 2.4]])
  
−
== Описание свойств и структуры алгоритма ==
+
== Description of the properties and structure of the algorithm ==
  
−
=== Общее описание алгоритма ===
+
=== General description ===
  
−
'''Перемножение матриц''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
+
'''Matrix multiplication''' is one of the basic procedures in algorithmic linear algebra, which is widely used in a number of different methods. Here, we consider the product <math>С = AВ</math>&nbsp; of dense real matrices (serial real version), that is, the version in which neither a special form of matrices nor the associative properties of the addition operation are used.  
−
Здесь мы рассмотрим умножение <math>С = AВ</math>&nbsp; плотных неособенных матриц (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения.
 
  
−
=== Математическое описание ===
+
=== Mathematical description ===
  
−
Исходные данные: плотная матрица <math>A</math> (элементы <math>a_{ij}</math>), плотная матрица <math>B</math> (элементы <math>b_{ij}</math>).
+
Input data: dense matrix <math>A</math> of size m-by-n (with entries <math>a_{ij}</math>), dense matrix <math>B</math> of size n-by-l (with entries <math>b_{ij}</math>).
  
−
Вычисляемые данные: плотная матрица <math>C</math> (элементы <math>c_{ij}</math>).
+
Output data: dense matrix <math>C</math> (with entries <math>c_{ij}</math>).
  
−
Формулы метода:
+
Formulas of the method:
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
Line 21: Line 20:
 
</math>
 
</math>
  
−
Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
+
There exists also a block version of the method; however, this description treats only the pointwise version.  
  
−
=== Вычислительное ядро алгоритма ===
+
=== Computational kernel of the algorithm ===
  
−
Вычислительное ядро перемножения плотных неособенных матриц можно составить из множественных (всего их <math>l</math>) вычислений умножения матрицы <math>A</math> на столбцы матрицы <math>B</math>, или (при более детальном рассмотрении), из множественных (всего их <math>ml</math>) скалярных произведений строк матрицы <math>A</math> на столбцы матрицы <math>B</math>:
+
The computational kernel of the dense matrix multiplication can be compiled of repeated products of <math>A</math> with the columns of <math>B</math> (there are on the whole <math>l</math> such products) or (upon more detailed inspection) of repeated dot products of the rows of <math>A</math> and the columns of <math>B</math> (there are on the whole <math>ml</math> such products):
  
 
:<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math>  
 
:<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math>  
  
−
в режиме накопления или без него, в зависимости от требований задачи.
+
Depending on the problem requirements, these sums are calculated with or without using the accumulation mode.  
  
−
=== Макроструктура алгоритма ===
+
=== Macrostructure of the algorithm ===
  
−
Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матрицы на вектор составляют множественные (всего <math>ml</math>) вычисления скалярных произведений строк матрицы <math>A</math> на столбцы матрицы <math>B</math>
+
As already noted in [[#Computational kernel of the algorithm|computational kernel of the algorithm description]], the basic part of the dense matrix multiplication is compiled of repeated dot products of the rows of <math>A</math> and the columns of <math>B</math> (there are on the whole <math>ml</math> such products):
  
 
:<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math>  
 
:<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math>  
  
−
в режиме накопления или без него.
+
These calculations are performed with or without using the accumulation mode.  
  
−
=== Описание схемы реализации последовательного алгоритма ===
+
=== Implementation scheme of the serial algorithm ===
  
−
Для всех <math>i</math> от <math>1</math> до <math>m</math>  и для всех <math>j</math> от <math>1</math> до <math>l</math> выполняются
+
For all <math>i</math> from <math>1</math> to <math>m</math>  and for all <math>j</math> from <math>1</math> to <math>l</math>, do
  
 
:<math>c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}</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>, вначале все элементы инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.
+
We emphasize that sums of the form <math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math> are calculated in the accumulation mode by adding the products <math>a_{ik} b_{kj}</math> to the current (temporary) value of <math>c_{ij}</math>.The index <math>k</math> '''increases''' from <math>1</math> to <math>n</math>. All the sums are initialized to zero. The general scheme is virtually the same if summations are performed in the decreasing order of indices; therefore, this case is not considered. Other orders of summation change the parallel properties of the algorithm and are considered in separate descriptions.  
  
−
=== Последовательная сложность алгоритма ===
+
=== Serial complexity of the algorithm ===
  
−
Для умножения двух квадратных матриц порядка <math>n</math> (т.е. при <math>m=n=l</math>) в последовательном (наиболее быстром) варианте требуется:
+
The multiplication of two square matrices of order <math>n</math> (that is, <math>m=n=l</math>) in the (fastest) serial version requires
−
 
−
* по <math>n^3</math> умножений и сложений.
 
  
−
Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на матрицу размером <math>m</math> строк на <math>n</math> столбцов в последовательном (наиболее быстром) варианте требуется:
+
* <math>n^3</math> multiplications and the same number of additions.
  
−
* по <math>mnl</math> умножений и сложений.
+
The multiplication of an <math>m</math>-by-<math>n</math> matrix by an <math>n</math>-by-<math>l</math> matrix in the (fastest) serial version requires
−
 
−
При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матрицы на вектор.
 
  
−
При классификации по последовательной сложности, таким образом, алгоритм умножения матриц относится к алгоритмам ''с кубической сложностью'' (в случае неквадратных матриц - с ''трилинейной'').
+
* <math>mnl</math> multiplications and the same number of additions.  
  
−
=== Информационный граф ===
+
The use of accumulation requires that multiplications and subtractions be done in the double precision mode (or such procedures as the Fortran function DPROD be used). This increases the computation time for performing the matrix multiplication.
  
−
Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.
+
In terms of serial complexity, the forward substitution is qualified as a ''cubic complexity'' algorithm (or a ''trilinear complexity'' algorithm if the matrices are rectangular).
  
−
Граф алгоритма умножения плотных матриц состоит из одной группы вершин, расположенной в целочисленных узлах трёхмерной области, соответствующая ей операция  <math>a+bc</math>.
+
=== Information graph ===
  
−
Естественно введённые координаты области таковы:
+
We describe the [[глоссарий#Граф алгоритма|algorithm graph]] both analytically and graphically.  
−
* <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>, принимая все целочисленные значения.
 
  
−
Аргументы операции следующие:
+
The algorithm graph of multiplying dense matrices consists of a single group of vertices placed at integer nodes of a three-dimensional domain. The corresponding operation is
−
*<math>a</math>:
+
<math>a+bc</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>;
 
  
−
Результат срабатывания операции является:
+
The natural coordinates of this domain are as follows:
−
** при <math>k < n</math> - ''промежуточным данным'' алгоритма;
+
* <math>i</math> varies from <math>1</math> to <math>m</math>, taking all the integer values in this range;
−
** при <math>k = n</math> - выходным данным <math>c_{ij}</math>.
+
* <math>j</math> varies from <math>1</math> to <math>l</math>, taking all the integer values in this range;
 +
* <math>k</math> varies from <math>1</math> to <math>n</math>, taking all the integer values in this range.  
  
−
[[file:Dense mtrx product.png|thumb|center|800px|Умножение плотных матриц с отображением выходных данных]]
+
The arguments of the operation are as follows:
 +
*<math>a</math> is:
 +
** the constant <math>0</math> if <math>k = 1</math>;
 +
** the result of performing the operation corresponding to the vertex with coordinates <math>i, j, k-1</math> if <math>k > 1</math>;
 +
*<math>b</math> is the element <math>a_{ik}</math> of the ''input data'';
 +
*<math>c</math> is the element <math>b_{kj}</math> of the ''input data'';
  
−
=== Описание ресурса параллелизма алгоритма ===
+
The result of performing the operation is:
 +
* an intermediate data item if <math>k < n</math>;
 +
* an output data item <math>c_{ij}</math> if <math>k = n</math>.
  
−
Для алгоритма умножения квадратных матриц порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:
+
[[file:Dense mtrx product.png|thumb|center|800px|Multiplication of dense matrices with demonstration of the output data]]
  
−
* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n^2</math> операций).
+
=== Parallelism resource of the algorithm ===
  
−
Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на матрицу размером <math>n</math> строк на <math>l</math> столбцов в последовательном (наиболее быстром) варианте требуется:
+
The parallel version of the algorithm for multiplying square matrices of order n requires that the following layers be successively performed:  
−
 
−
* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>ml</math> операций).
 
  
−
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.
+
* <math>n</math> layers of multiplications and the same numbers of layers for addition (there are <math>n^2</math> operations in each layer).
  
−
При классификации по высоте ЯПФ, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''квадратичной'' (для квадратных матриц) или ''билинейной'' (для матриц общего вида).
+
The multiplication of an <math>m</math>-by-<math>n</math> matrix by an <math>n</math>-by-<math>l</math> matrix in the (fastest) serial version requires
  
−
=== Описание входных и выходных данных ===
+
* <math>n</math> layers of multiplications and the same numbers of layers for addition (there are <math>ml</math> operations in each layer).
  
−
'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), матрица <math>B</math> (элементы <math>b_{ij}</math>)).
+
The use of accumulation requires that multiplications and subtractions be done in the double precision mode. For the parallel version, this implies that virtually all the intermediate calculations in the algorithm must be performed in double precision if the accumulation option is used. Unlike the situation with the serial version, this results in a certain increase in the required memory size.  
  
−
'''Объём входных данных''': <math>mn+nl</math>
+
In terms of the parallel form height, the dense matrix multiplication is qualified as a quadratic complexity algorithm. In terms of the parallel form width, its complexity is also ''quadratic'' (for square matrices) or ''bilinear'' (for general rectangular matrices).
  
−
'''Выходные данные''': матрица <math>C</math> (элементы <math>c_{ij}</math>).
+
=== Description of the input and output data ===
  
−
'''Объём выходных данных''': <math>ml</math>
+
'''Input data''': matrix <math>A</math> (with entries <math>a_{ij}</math>), matrix <math>B</math> (with entries <math>b_{ij}</math>)).
  
−
=== Свойства алгоритма ===
+
'''Size of the input data ''': <math>mn+nl</math>
  
−
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''квадратичным'' или ''билинейным'' (отношение кубической или трилинейной к линейной).  
+
'''Output data ''': matrix <math>C</math> (with entries <math>c_{ij}</math>).
  
−
При этом вычислительная мощность алгоритма умножения матриц, как отношение числа операций к суммарному объему входных и выходных данных – ''линейно''.
+
''''''Size of the output data''': <math>ml</math>
  
−
При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.
+
=== Properties of the algorithm ===
 +
 
 +
It is clear that, in the case of unlimited resources, the ratio of the serial to parallel complexity is ''quadratic'' or ''bilinear'' (since this is the ratio of the cubic or trilinear complexity to linear one).  
 +
 
 +
The computational power of the dense matrix multiplication, understood as the ratio of the number of operations to the total size of the input and output data, is ''linear''.
 +
 
 +
The algorithm of dense matrix multiplication is completely determined. We do not consider any other order of performing associative operations in this version.  
  
 
[[Ru:Перемножение плотных неособенных матриц (последовательный вещественный вариант)]]
 
[[Ru:Перемножение плотных неособенных матриц (последовательный вещественный вариант)]]
  
 
[[Category:Started articles]]
 
[[Category:Started articles]]

Revision as of 11:30, 15 July 2015

Primary authors of this description: A.V.Frolov, Vad.V.Voevodin (Section 2.2), A.M.Teplov (раздел Section 2.4)

1 Description of the properties and structure of the algorithm

1.1 General description

Matrix multiplication is one of the basic procedures in algorithmic linear algebra, which is widely used in a number of different methods. Here, we consider the product [math]С = AВ[/math]  of dense real matrices (serial real version), that is, the version in which neither a special form of matrices nor the associative properties of the addition operation are used.

1.2 Mathematical description

Input data: dense matrix [math]A[/math] of size m-by-n (with entries [math]a_{ij}[/math]), dense matrix [math]B[/math] of size n-by-l (with entries [math]b_{ij}[/math]).

Output data: dense matrix [math]C[/math] (with entries [math]c_{ij}[/math]).

Formulas of the method:

[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]

There exists also a block version of the method; however, this description treats only the pointwise version.

1.3 Computational kernel of the algorithm

The computational kernel of the dense matrix multiplication can be compiled of repeated products of [math]A[/math] with the columns of [math]B[/math] (there are on the whole [math]l[/math] such products) or (upon more detailed inspection) of repeated dot products of the rows of [math]A[/math] and the columns of [math]B[/math] (there are on the whole [math]ml[/math] such products):

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

Depending on the problem requirements, these sums are calculated with or without using the accumulation mode.

1.4 Macrostructure of the algorithm

As already noted in computational kernel of the algorithm description, the basic part of the dense matrix multiplication is compiled of repeated dot products of the rows of [math]A[/math] and the columns of [math]B[/math] (there are on the whole [math]ml[/math] such products):

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

These calculations are performed with or without using the accumulation mode.

1.5 Implementation scheme of the serial algorithm

For all [math]i[/math] from [math]1[/math] to [math]m[/math] and for all [math]j[/math] from [math]1[/math] to [math]l[/math], do

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

We emphasize that sums of the form [math]\sum_{k = 1}^{n} a_{ik} b_{kj}[/math] are calculated in the accumulation mode by adding the products [math]a_{ik} b_{kj}[/math] to the current (temporary) value of [math]c_{ij}[/math].The index [math]k[/math] increases from [math]1[/math] to [math]n[/math]. All the sums are initialized to zero. The general scheme is virtually the same if summations are performed in the decreasing order of indices; therefore, this case is not considered. Other orders of summation change the parallel properties of the algorithm and are considered in separate descriptions.

1.6 Serial complexity of the algorithm

The multiplication of two square matrices of order [math]n[/math] (that is, [math]m=n=l[/math]) in the (fastest) serial version requires

  • [math]n^3[/math] multiplications and the same number of additions.

The multiplication of an [math]m[/math]-by-[math]n[/math] matrix by an [math]n[/math]-by-[math]l[/math] matrix in the (fastest) serial version requires

  • [math]mnl[/math] multiplications and the same number of additions.

The use of accumulation requires that multiplications and subtractions be done in the double precision mode (or such procedures as the Fortran function DPROD be used). This increases the computation time for performing the matrix multiplication.

In terms of serial complexity, the forward substitution is qualified as a cubic complexity algorithm (or a trilinear complexity algorithm if the matrices are rectangular).

1.7 Information graph

We describe the algorithm graph both analytically and graphically.

The algorithm graph of multiplying dense matrices consists of a single group of vertices placed at integer nodes of a three-dimensional domain. The corresponding operation is [math]a+bc[/math].

The natural coordinates of this domain are as follows:

  • [math]i[/math] varies from [math]1[/math] to [math]m[/math], taking all the integer values in this range;
  • [math]j[/math] varies from [math]1[/math] to [math]l[/math], taking all the integer values in this range;
  • [math]k[/math] varies from [math]1[/math] to [math]n[/math], taking all the integer values in this range.

The arguments of the operation are as follows:

  • [math]a[/math] is:
    • the constant [math]0[/math] if [math]k = 1[/math];
    • the result of performing the operation corresponding to the vertex with coordinates [math]i, j, k-1[/math] if [math]k \gt 1[/math];
  • [math]b[/math] is the element [math]a_{ik}[/math] of the input data;
  • [math]c[/math] is the element [math]b_{kj}[/math] of the input data;

The result of performing the operation is:

  • an intermediate data item if [math]k \lt n[/math];
  • an output data item [math]c_{ij}[/math] if [math]k = n[/math].
Multiplication of dense matrices with demonstration of the output data

1.8 Parallelism resource of the algorithm

The parallel version of the algorithm for multiplying square matrices of order n requires that the following layers be successively performed:

  • [math]n[/math] layers of multiplications and the same numbers of layers for addition (there are [math]n^2[/math] operations in each layer).

The multiplication of an [math]m[/math]-by-[math]n[/math] matrix by an [math]n[/math]-by-[math]l[/math] matrix in the (fastest) serial version requires

  • [math]n[/math] layers of multiplications and the same numbers of layers for addition (there are [math]ml[/math] operations in each layer).

The use of accumulation requires that multiplications and subtractions be done in the double precision mode. For the parallel version, this implies that virtually all the intermediate calculations in the algorithm must be performed in double precision if the accumulation option is used. Unlike the situation with the serial version, this results in a certain increase in the required memory size.

In terms of the parallel form height, the dense matrix multiplication is qualified as a quadratic complexity algorithm. In terms of the parallel form width, its complexity is also quadratic (for square matrices) or bilinear (for general rectangular matrices).

1.9 Description of the input and output data

Input data: matrix [math]A[/math] (with entries [math]a_{ij}[/math]), matrix [math]B[/math] (with entries [math]b_{ij}[/math])).

Size of the input data : [math]mn+nl[/math]

Output data : matrix [math]C[/math] (with entries [math]c_{ij}[/math]).

'Size of the output data: [math]ml[/math]

1.10 Properties of the algorithm

It is clear that, in the case of unlimited resources, the ratio of the serial to parallel complexity is quadratic or bilinear (since this is the ratio of the cubic or trilinear complexity to linear one).

The computational power of the dense matrix multiplication, understood as the ratio of the number of operations to the total size of the input and output data, is linear.

The algorithm of dense matrix multiplication is completely determined. We do not consider any other order of performing associative operations in this version.

Retrieved from "https://algowiki-project.org/algowiki/en/index.php?title=Dense_matrix_multiplication_(serial_version_for_real_matrices)&oldid=287"