Algorithm level

Difference between revisions of "Dense matrix-vector multiplication"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][checked revision]
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|2.4]])
+
{{level-a}}
  
== Описание свойств и структуры алгоритма ==
+
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 implementation|Section 2.4]])
  
=== Общее описание алгоритма ===
+
== Properties and structure of the algorithm ==
  
'''Умножение матрицы на вектор''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
+
=== General description of the algorithm ===
Здесь мы рассмотрим умножение <math>y = Ax</math> плотной неособенной матрицы на вектор (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения.
 
  
=== Математическое описание ===
+
'''Matrix-vector 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>y = Ax</math> of a dense real matrix and a vector (serial real version), that is, the version in which neither a special form of the matrix nor the associative properties of the addition operation are used.
  
Исходные данные: плотная матрица <math>A</math> (элементы <math>a_{ij}</math>), умножаемый на неё вектор <math>x</math> (элементы <math>x_{i}</math>).
+
=== Mathematical description of the algorithm ===
  
Вычисляемые данные: вектор решения <math>y</math> (элементы <math>y_{i}</math>).
+
Input data: dense matrix <math>A</math> of size m-by-n (with entries <math>a_{ij}</math>), its vector cofactor <math>x</math> of dimension n (with components <math>x_{i}</math>).
  
Формулы метода:
+
Output data: vector <math>y</math> of dimension m (with components <math>y_{i}</math>).
 +
 
 +
Formulas of the method:
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
Line 21: Line 22:
 
</math>
 
</math>
  
Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
+
There also exists a block version of the method; however, this description treats only the pointwise version.  
  
=== Вычислительное ядро алгоритма ===
+
=== Computational kernel of the algorithm ===
  
Вычислительное ядро умножения матрицы на вектор можно составить из множественных (всего их <math>m</math>) вычислений скалярных произведений строк матрицы <math>A</math> вектор <math>x</math>:
+
The computational kernel of the dense matrix-vector multiplication can be compiled of repeated dot products of the rows of <math>A</math> and the vector <math>x</math> (there are on the whole <math>m</math> such products):
  
 
:<math> \sum_{j = 1}^{n} a_{ij} x_{j}</math>  
 
:<math> \sum_{j = 1}^{n} a_{ij} x_{j}</math>  
  
в режиме накопления или без него, в зависимости от требований задачи.
+
Depending on the problem requirements, these sums are calculated with or without using the accumulation mode.  
  
=== Макроструктура алгоритма ===
+
=== Macro structure of the algorithm ===
  
Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матрицы на вектор составляют множественные (всего <math>m</math>) вычисления скалярных произведений строк матрицы <math>A</math> вектор <math>x</math>
+
As already noted in the [[#Вычислительное ядро алгоритма|description of the computational kernel]], the basic part of the dense matrix-vector multiplication is compiled of repeated dot products of the rows of <math>A</math> and the vector <math>x</math> (there are on the whole <math>m</math> such products):
  
 
:<math> \sum_{j = 1}^{n} a_{ij} x_{j}</math>  
 
:<math> \sum_{j = 1}^{n} a_{ij} x_{j}</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> по возрастанию выполняются
+
For all <math>i</math> from <math>1</math> to <math>m</math>, do 
  
 
:<math>y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}</math>
 
:<math>y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}</math>
  
Особо отметим, что вычисления сумм вида <math>\sum_{j = 1}^{n} a_{ij} x_{j}</math> производят в режиме накопления прибавлением к текущему (временному) значению вычисляемой компоненты вектора <math>y_{i}</math> произведений <math>a_{ij} x_{j}</math> для <math>j</math> от <math>1</math> до <math>n</math>, '''c возрастанием''' <math>j</math>, вначале все компоненты инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.
+
We emphasize that sums of the form <math>\sum_{j = 1}^{n} a_{ij} x_{j}</math> are calculated in the accumulation mode by adding the products <math>a_{ij} x_{j}</math> to the current (temporary) value of the component <math>y_{i}</math>. The index <math>j</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 <math>j</math>; 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</math>) в последовательном (наиболее быстром) варианте требуется:
+
The multiplication of a square matrix of order <math>n</math> (that is, <math>m=n</math>) by a vector of the same dimension in the (fastest) serial version requires
 
 
* по <math>n^2</math> умножений и сложений.
+
* <math>n^2</math> multiplications and the same number of additions.
 +
 
 +
The multiplication of an <math>m</math>-by-<math>n</math> matrix by a vector of dimension <math>n</math> in the (fastest) serial version requires
 +
 
 +
* <math>mn</math> multiplications and the same number of additions.
 +
 
 +
The use of accumulation requires that multiplications and additions 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-vector multiplication.
 +
 
 +
In terms of serial complexity, the matrix-vector multiplication is qualified as a ''quadratic complexity'' algorithm (or a ''bilinear complexity'' algorithm if the matrix is rectangular).
 +
 
 +
=== Information graph ===
  
Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:
+
We describe the [[глоссарий#Граф алгоритма|algorithm graph]] both analytically and graphically.
  
* по <math>mn</math> умножений и сложений.
+
[[File:YeqAX.png|500px|thumb|center|Figure 1. Graph of the serial multiplication of a dense matrix by a vector with demonstration of the input and output data]]
 
При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матрицы на вектор.
 
  
При классификации по последовательной сложности, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам ''с квадратической сложностью'' (в случае неквадратной матрицы - с ''билинейной'').
+
The algorithm graph of multiplying a dense matrix by a vector consists of a single group of vertices placed at integer nodes of a two-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>n</math>, taking all the integer values in this range.  
  
[[File:YeqAX.png|500px|thumb|center|Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]
+
The arguments of the operation are as follows:
 +
*<math>a</math> is:
 +
** the constant <math>0</math> if <math>j = 1</math>;
 +
** the result of performing the operation corresponding to the vertex with coordinates <math>i, j -1</math> if <math>k > 1</math>;
 +
*<math>b</math> is the element <math>a_{ij}</math> of the ''input data'';
 +
*<math>c</math> is the element <math>x_{j}</math> of the ''input data''.  
  
 +
The result of performing the operation is:
 +
* an intermediate data item if <math>j < n</math>;
 +
* an output data item <math>c_{ij}</math> if <math>j = n</math>.
  
Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция  <math>a+bc</math>.  
+
The graph described can be seen in the figure corresponding to the case <math>m = 4, n = 5</math>. The vertices are depicted in blue. Only the supplies of the input data from the vector <math>x</math> are shown. The supplies of the entries of <math>A</math> to all the vertices are not shown.
  
Естественно введённые координаты области таковы:
+
=== Parallelization resource of the algorithm ===
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
 
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.
 
  
Аргументы операции следующие:
+
The parallel version of the algorithm for multiplying a square matrix of order n by a vector requires that the following layers be successively performed:  
*<math>a</math>:
 
** при <math>j = 1</math> константа <math>0.</math>;
 
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
 
*<math>b</math> — элемент ''входных данных'', а именно  <math>a_{ij}</math>;
 
*<math>c</math> - элемент входных данных <math>x_{j}</math>;
 
  
Результат срабатывания операции является:
+
* <math>n</math> layers of multiplications and the same number of layers for addition (there are <math>n</math> operations in each layer).
** при <math>j < n</math> - ''промежуточным данным'' алгоритма;
 
** при <math>j = n</math> - выходным данным.
 
  
Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.
+
The multiplication of an <math>m</math>-by-<math>n</math> matrix by a vector of dimension <math>n</math> in the (fastest) serial version requires
  
=== Описание ресурса параллелизма алгоритма ===
+
* <math>n</math> layers of multiplications and the same number of layers for addition (there are <math>m</math> operations in each layer).
  
Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:
+
The use of accumulation requires that multiplications and additions 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>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).
+
In terms of the parallel form height, the dense matrix-vector multiplication is qualified as a linear complexity algorithm. In terms of the parallel form width, its complexity is also ''linear''.
  
Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:
+
=== Input and output data of the algorithm ===
 
* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).
 
  
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.
+
'''Input data''': matrix <math>A</math> (with entries <math>a_{ij}</math>), vector <math>x</math> (with components <math>x_{i}</math>).
  
При классификации по высоте ЯПФ, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''линейной''.
+
'''Size of the input data ''': <math>mn+n</math> .  
  
=== Описание входных и выходных данных ===
+
'''Output data ''': vector <math>y</math> (with components <math>y_{i}</math>).
  
'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>x</math> (элементы <math>x_{i}</math>).
+
'''Size of the output data''': <math>m</math>.
  
'''Объём входных данных''': <math>mn+n</math> .
+
=== Properties of the algorithm ===
  
'''Выходные данные''': вектор <math>y</math> (элементы <math>y_{i}</math>).
+
It is clear that, in the case of unlimited resources, the ratio of the serial to parallel complexity is ''linear'' (since this is the ratio of the quadratic or bilinear complexity to linear one).  
  
'''Объём выходных данных''': <math>m</math>.
+
The computational power of the dense matrix-vector multiplication, understood as the ratio of the number of operations to the total size of the input and output data, is only a ''constant''.
  
=== Свойства алгоритма ===
+
The algorithm of dense matrix-vector multiplication is completely determined. We do not consider any other order of performing associative operations in this version.
  
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).
+
== Software implementation of the algorithm ==
 +
=== Implementation peculiarities of the serial algorithm ===
 +
=== Possible methods and considerations for parallel implementation of the algorithm  ===
 +
=== Run results ===
 +
=== Conclusions for different classes of computer architecture ===
  
При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.
+
== References ==
  
При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.
+
<references />
  
 
[[Ru:Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]]
 
[[Ru:Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]]
  
[[Category:Started articles]]
+
[[Category:Articles in progress]]

Latest revision as of 12:54, 8 July 2022


Primary authors of this description: A.V.Frolov, Vad.V.Voevodin (Section 2.2), A.M.Teplov (Section 2.4)

1 Properties and structure of the algorithm

1.1 General description of the algorithm

Matrix-vector 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]y = Ax[/math] of a dense real matrix and a vector (serial real version), that is, the version in which neither a special form of the matrix nor the associative properties of the addition operation are used.

1.2 Mathematical description of the algorithm

Input data: dense matrix [math]A[/math] of size m-by-n (with entries [math]a_{ij}[/math]), its vector cofactor [math]x[/math] of dimension n (with components [math]x_{i}[/math]).

Output data: vector [math]y[/math] of dimension m (with components [math]y_{i}[/math]).

Formulas of the method:

[math] \begin{align} y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}, \quad i \in [1, m]. \end{align} [/math]

There also exists 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-vector multiplication can be compiled of repeated dot products of the rows of [math]A[/math] and the vector [math]x[/math] (there are on the whole [math]m[/math] such products):

[math] \sum_{j = 1}^{n} a_{ij} x_{j}[/math]

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

1.4 Macro structure of the algorithm

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

[math] \sum_{j = 1}^{n} a_{ij} x_{j}[/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], do

[math]y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}[/math]

We emphasize that sums of the form [math]\sum_{j = 1}^{n} a_{ij} x_{j}[/math] are calculated in the accumulation mode by adding the products [math]a_{ij} x_{j}[/math] to the current (temporary) value of the component [math]y_{i}[/math]. The index [math]j[/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 [math]j[/math]; 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 a square matrix of order [math]n[/math] (that is, [math]m=n[/math]) by a vector of the same dimension in the (fastest) serial version requires

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

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

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

The use of accumulation requires that multiplications and additions 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-vector multiplication.

In terms of serial complexity, the matrix-vector multiplication is qualified as a quadratic complexity algorithm (or a bilinear complexity algorithm if the matrix is rectangular).

1.7 Information graph

We describe the algorithm graph both analytically and graphically.

Figure 1. Graph of the serial multiplication of a dense matrix by a vector with demonstration of the input and output data

The algorithm graph of multiplying a dense matrix by a vector consists of a single group of vertices placed at integer nodes of a two-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]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]j = 1[/math];
    • the result of performing the operation corresponding to the vertex with coordinates [math]i, j -1[/math] if [math]k \gt 1[/math];
  • [math]b[/math] is the element [math]a_{ij}[/math] of the input data;
  • [math]c[/math] is the element [math]x_{j}[/math] of the input data.

The result of performing the operation is:

  • an intermediate data item if [math]j \lt n[/math];
  • an output data item [math]c_{ij}[/math] if [math]j = n[/math].

The graph described can be seen in the figure corresponding to the case [math]m = 4, n = 5[/math]. The vertices are depicted in blue. Only the supplies of the input data from the vector [math]x[/math] are shown. The supplies of the entries of [math]A[/math] to all the vertices are not shown.

1.8 Parallelization resource of the algorithm

The parallel version of the algorithm for multiplying a square matrix of order n by a vector requires that the following layers be successively performed:

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

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

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

The use of accumulation requires that multiplications and additions 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-vector multiplication is qualified as a linear complexity algorithm. In terms of the parallel form width, its complexity is also linear.

1.9 Input and output data of the algorithm

Input data: matrix [math]A[/math] (with entries [math]a_{ij}[/math]), vector [math]x[/math] (with components [math]x_{i}[/math]).

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

Output data : vector [math]y[/math] (with components [math]y_{i}[/math]).

Size of the output data: [math]m[/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 linear (since this is the ratio of the quadratic or bilinear complexity to linear one).

The computational power of the dense matrix-vector multiplication, understood as the ratio of the number of operations to the total size of the input and output data, is only a constant.

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

2 Software implementation of the algorithm

2.1 Implementation peculiarities of the serial algorithm

2.2 Possible methods and considerations for parallel implementation of the algorithm

2.3 Run results

2.4 Conclusions for different classes of computer architecture

3 References