Алговики - Вклад [ru]

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-11-20T20:33:49Z

Lexaloris:

{{Assignment}}

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

Кочетков Павел ответственен за программную реализацию алгоритма, Новоселов Алексей ответственен за оформление статьи.

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора <math>B</math> можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Параллельная реализация алгоритма позволяет до некоторой степени сократить время вычислений в несколько раз.
На вычислительном комплексе ''IBM Blue Gene/P'' было проведено экспериментальное исследование масштабируемости программной реализации умножения разряженной матрицы на вектор. Результаты исследования представлены на рис.2:

[[Файл:DependeceOfTheExecutionTime.jpg |thumb|center|900px|Рисунок 2. График зависимости времени выполнения программы умножения разряженной матрицы на вектор от количества ненулевых элементов матрицы для данного числа процессоров.]]

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

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-11-20T20:20:07Z

Lexaloris: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

Кочетков Павел ответственен за программную реализацию алгоритма, Новоселов Алексей ответственен за оформление статьи.

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора <math>B</math> можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Параллельная реализация алгоритма позволяет до некоторой степени сократить время вычислений в несколько раз.
На вычислительном комплексе ''IBM Blue Gene/P'' было проведено экспериментальное исследование масштабируемости программной реализации умножения разряженной матрицы на вектор. Результаты исследования представлены на рис.2:

[[Файл:DependeceOfTheExecutionTime.jpg |thumb|center|900px|Рисунок 2. График зависимости времени выполнения программы умножения разряженной матрицы на вектор от количества ненулевых элементов матрицы для данного числа процессоров.]]

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

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-11-20T20:09:40Z

Lexaloris: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

Кочетков Павел ответственен за программную реализацию алгоритма, Новоселов Алексей ответственен за оформление статьи.

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора <math>B</math> можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

[[Файл:DependeceOfTheExecutionTime.jpg |thumb|center|900px|Рисунок 2. График зависимости времени выполнения программы умножения разряженной матрицы на вектор от количества ненулевых элементов матрицы для данного числа процессоров.]]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-11-20T20:01:45Z

Lexaloris: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

Кочетков Павел ответственен за программную реализацию алгоритма, Новоселов Алексей ответственен за оформление статьи.

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора <math>B</math> можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

[[Файл:DependeceOfTheExecutionTime.jpg]]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-11-20T19:59:35Z

Lexaloris: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

Кочетков Павел ответственен за программную реализацию алгоритма, Новоселов Алексей ответственен за оформление статьи.

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора <math>B</math> можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

[[Файл:Example.jpg]]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-11-01T14:42:51Z

Lexaloris:

{{Assignment}}

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

Кочетков Павел ответственен за программную реализацию алгоритма, Новоселов Алексей ответственен за оформление статьи.

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора <math>B</math> можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-11-01T14:34:32Z

Lexaloris:

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

Кочетков Павел ответственен за программную реализацию алгоритма, Новоселов Алексей ответственен за оформление статьи.

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора <math>B</math> можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-11-01T14:33:03Z

Lexaloris:

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]
Кочетков Павел ответственен за программную реализацию алгоритма, Новоселов Алексей ответственен за оформление статьи.

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора <math>B</math> можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T20:03:57Z

Lexaloris:

{{Assignment}}

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора <math>B</math> можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T19:34:39Z

Lexaloris:

{{Assignment}}

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора B можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Обсуждение участника:Lineprinter

2016-10-15T19:03:17Z

Lexaloris: /* Перенос */

== Перенос ==
Статья: [[Кластеризация сетями Кохонена]]
Выполняют: [[Участник:Kravtsovkirill| Кравцов Кирилл]] и [[Участник:Emaksimov| Максимов Егор]]

Статья: [[Нахождение собственных чисел квадратной матрицы методом QR разложения (2)]]
Выполняют: Баев Олег и Шевелев Александр

Статья: [[Стабилизированный метод биспоряженных градиентов (BiCGSTAB)]]
Выполняют: Гаврилов Алексей и Новиков Александр

Статья: [[Участники: Бобошко А., Юмакаева А./Решение начальной задачи Коши для системы ОДУ методом Рунге-Кутта 4-го порядка]];
Выполняют: Бобошко Алексей и Юмакаева Алина

Статья: [[Алгоритм кластеризации, основанный на сетях Кохоннена]];
Выполняют: Логвиненко Александра и Адиев Тохтар

Статья: [[Ортогонализация Грама-Шмидта]];
Выполняют: [[Участник:KibAndrey| Кибанов Андрей]] и Аджиева Татьяна

Статья: [[Самоорганизующиеся карты Кохонена]];
Выполняет: [[Участник:Anton goy| Гой Антон]]

Статья:[[ЕМ-алгоритм_(Тематическое_моделирование)]];
Выполняют: Мурат Апишев и Андрей Заночкин

Статья:[[Алгоритм_Ланцоша_с_полной_переортогонализацией]];
Выполняет:[[Участник:Sfedotov| Федотов С.А.]]

Статья: [[Алгоритм_k-средних]]
Выполняют: [[Участник:Error2407|Богомазов Евгений]], [[Участник:Илья_Егоров|Егоров Илья]]

Статья: [[Алгоритм k-means]]
Выполняют: [[Участник:Бротиковская Данута|Данута Бротиковская]] и [[Участник:DennZo1993|Денис Зобнин]]

Статья: [[Нечеткий_алгоритм_С_средних]]
Выполняют: [[Участник:Demon smd|Д.А.Гуськов]], [[Участник:marina abramenkova|М.А.Абраменкова]]

Статья: [[Решение_задачи_Коши_для_системы_ОДУ_методом_Рунге-Кутты_4_порядка]];
Выполняют: [[Участник:Алимов_Дамир_Алиевич|Алимов Дамир]] и [[Участник:Anlesnichiy|Антон Лесничий]]

Статья: [[Строгий_алгоритм_С_средних_(Hard_C-Means,_HCM)]];
Выполняют: [[Участник:Светлана_Лукьяненко|Лукьяненко Светлана]] и [[Участник:Юрий_Комаров|Комаров Юрий]]

Статья: [[Алгоритм кластеризации, основанный на минимальном остовном дереве]];
Выполняет: [[Участник:Astandrik | Стандрик Антон Сергеевич]]

Статья: [[Умножение разреженной матрицы на вектор]];
Выполняет: [[Участник:Lexaloris | Новоселов Алексей]], Выполняет: [[Участник:kochet|П.А. Кочетков]]

Статья: [[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(3)|Нахождение собственных чисел квадратной матрицы методом QR разложения (3)]];
Выполняют: [[Участник:Смирнова_Александра|Смирнова А.С.]], [[Участник:Александра_Киямова|Киямова А.]]

Статья: [[Метод_Якоби_вычисления_сингулярных_чисел_и_векторов]];
Выполняют: [[Участница:Почернина_Елена| Почернина Елена]] и [[Участница:Светлана|Костюкова Светлана]]

Статья: [[Метод_Ньютона_для_решения_систем_нелинейных_уравнений(2)]];
Выполняют: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений]];
Выполняют: [[Участник:Cookie|Шатков С.А.]], [[Участница:JuliaA|Антохина Ю.А.]]

Статья: [[Быстрое_преобразование_Фурье_(FFT)|Быстрое преобразование Фурье (FFT)]];
Выполняют: [[Участник:Victoria_Stepanischeva|Степанищева Виктория]] и [[Участник:Igor_Munkin|Мунькин Игорь]]

Статья: [[Быстрое_дискретное_преобразование_Фурье|Быстрое_дискретное_преобразование_Фурье]];
Выполняют: [[Участник:ivanov.kir.m | К.М.Иванов]], [[Участник:Pumpkin | А.C.Сапин]]

Статья:[[Алгоритм_k_средних]]
Выполняют: [[Участник:Parkhomenko|Пархоменко Павел]], [[Участник:ivan.mashonskiy|Машонский Иван]]

Статья:[[EM-алгоритм_кластеризации]]
Выполняет: [[Участник:Noite|Зинченко Дмитрий]]

Статья:[[Алгоритм_k_means]]
Выполняют: [[Участник:IanaV| Валуйская Яна]], [[Участник:GlotovES| Глотов Евгений]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы ЗП |Метод Якоби вычисления собственных значений симметричной матрицы ЗП]];
Выполняют: [[Участник:Зиновьев Владимир|Зиновьев В.С.]], [[Участник:Пронин Андрей|Пронин А.М.]]

Статья:[[Алгоритм_кластеризации,_основанный_на_минимальном_покрывающем_дереве]]
Выполняет: [[Участник:Kanast74|Дмитриева Анастасия]]

Статья:[[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(4)]]
Выполняют: [[Участник:F-morozov|Морозов Ф. В.]], [[Участник:Nataliya|Пащенко Н. Ф.]]

Статья:[[Хранение_ненулевых_элементов_разреженных_матриц._Умножение_разреженной_матрицы_на_вектор]];
Выполняют: [[Участник:Trrufina|Третьякова Р.М.]] и [[Участник:Екатерина_Буторина|Буторина Е.В.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений2]];
Выполняет: [[Участник:Лукьянова Анна|Лукьянова А.Я.]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы]];
Выполняют: [[Участник: Galkina|Галкина А.С.]], [[Участник: Игорь|Плахов И.А.]]

Статья: [[Метод рекурсивной координатной бисекции]];
Выполняют: [[Участник: Obirvalger|Гордеев Михаил]], [[Участник: KolmakovEA|Колмаков Евгений]]

Статья: [[Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок)]];
Выполняют: [[Участник: Эльвира Ахиярова|Ахиярова Эльвира]]

Статья: [[Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор]];
Выполняют: [[Участник: Janyell|Сычева Евгения]], [[Участник: Ahahalin|Хахалин Анатолий]]

Статья: [[Построение матрицы Адамара произвольного размера]];
Выполняют: [[Участник: Бугаков Юрий|Бугаков Юрий]], Кужамалиев Ернур

Статья: [[Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки (1)]]
Выполняют: [[Участница:Sannikovats| Санникова Татьяна Сергеевна]], [[Участник:Plukshin| Лукшин Петр Андреевич]]

Статья: [[Алгоритм кластеризации, основанный на построении каркаса]];
Выполняют: [[Участник:SenderovichNikita| Сендерович Никита]]

Статья: [[Алгоритм кластеризации, основанный на максимизации ожидания]];
Выполняют: Готман Мария, Лукашкина Юлия

Статья: [[Partitioning_Around_Medoids_(PAM)]]
Выполняют: [[Участник:Avasilenko|А.Э.Василенко]], [[Участник:Anastasia|А.В.Тузикова]]

Статья: [[Нечеткий алгоритм С-средних (Fuzzy C-means)]]
Выполняют: [[Участник:Nikmedoed|Н.А. Муромцев]], [[Участник:illusive_mike|М.С. Дворецкий]]

Статья: [[Нечеткий алгоритм C средних]]
Выполняют: [[Участник:Gkhazeeva|Гелана Хазеева]], [[Участник:Yushin|Павел Юшин]]

Статья: [[Плотностный алгоритм кластеризации DBSCAN]]
Выполняют: [[Участник:Elena777mc|Малахова Е.С.]], [[Участник:Жаннат_Сагиолданова|Сагиолданова Ж.]]

Статья: [[Кластеризация Partitioning Around Medoids (PAM)]]
Выполняют:[[ Участник:Тодуа Антон| Тодуа Антон]], [[Участник:Гусева Юлия| Гусева Юлия]]

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T18:59:27Z

Lexaloris: /* Свойства алгоритма */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора B можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T18:47:23Z

Lexaloris: /* Литература */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора B можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов равно <math>O(\frac{k}{N})</math>

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

* [1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
* [2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T18:47:08Z

Lexaloris: /* Литература */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора B можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов равно <math>O(\frac{k}{N})</math>

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

[1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.
[2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T18:44:22Z

Lexaloris: /* Существующие реализации алгоритма */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора B можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов равно <math>O(\frac{k}{N})</math>

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

Алгоритм релизован в составе библиотек:
* SparseLib++[http://math.nist.gov/sparselib++/]
* cuSPARSE [http://docs.nvidia.com/cuda/cusparse/]
* uBLAS [http://www.boost.org/doc/libs/1_62_0/libs/numeric/ublas/doc/]
* Intel MKL [https://software.intel.com/en-us/intel-mkl]

= Литература =

[1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T18:41:07Z

Lexaloris: /* Свойства алгоритма */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора B можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов равно <math>O(\frac{k}{N})</math>

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

[1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T18:28:51Z

Lexaloris: /* Ресурс параллелизма алгоритма */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

Алгоритм обладает возможностью выполняться параллельно, что позволяет значительно ускорить вычисления.
Вычисление значения каждого элемента вектора-произведения для каждой строки матрицы и элемента вектора B можно проводить на отдельных процессорах.
Максимальная эффективность вычислений достигается при наличии не менее, чем <math>N</math> процессоров, т.е отдельный процессор на вычисление значения каждого элемента вектора-произведения. На процессоре выполняется <math>k(i)</math> последовательных операций умножения и сложения. Поэтому число ярусов для <math>i</math>-ого процессора равно <math>k(i)</math>.

Для параллельного выполнения алгоритма требуется:

* <math>N</math> ярусов умножений и сложений,
* в каждом из ярусов <math>k << m</math> операций.

При классификации по высоте ЯПФ, алгоритм имеет линейную сложность. При классификации по высоте ЯПФ также линейную.

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

[1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T17:43:57Z

Lexaloris: /* Информационный граф */

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

На рисунке 1 изображен информационный граф алгоритма.

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

[1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T17:42:35Z

Lexaloris:

{{algorithm
| name = Умножение разреженной матрицы на вектор
| serial_complexity = <math>O(k)</math>
| pf_height = <math>O(m)</math>
| pf_width = <math>O(n)</math>
| input_data = <math>k + m</math>
| output_data = <math>n</math>
}}

'''Авторы страницы:''' [[Участник:Lexaloris|A.Д. Новоселов]] и [[Участник:kochet|П.А. Кочетков]]

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

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

=== Хранение ненулевых элементов разреженной матрицы ===

==== Разреженный строчной формат ====

Одной из наиболее широко используемых схем хранения разреженных матриц является ''разреженный строчный формат''. Эта
схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для умножения разреженной матрицы на вектор.
Например, рассмотрим формат хранения разряженной матрицы <math>A</math>:

[[File:RRCOMatrix.png]]

Значения ненулевых элементов матрицы и соответствующие столбцовые индексы хранятся в этой схеме по строкам в двух массивах <math>AN</math> и <math>JA</math> соответственно. Используется также массив указателей <math>IA</math>, отмечающих позиции массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Дополнительная компонента в <math>IA</math> содержит указатель первой свободной позиции в <math>JA</math> и <math>AN</math>.

Таким образом <math>A</math> представляется в виде:

IA = [ 1 4 4 6 ]
JA = [ 3 4 8 6 8 ]
AN = [ 1 3 5 7 1 ]

Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, и ''упорядоченным'', поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов. Таким образом, это строчное представление, полное и упорядоченное, или сокращенно '''(RR (С) О)'''.

==== Неупорядоченное представление ====

Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк поддерживается, внутри каждой строки элементы могут храниться в произвольном порядке. Для матрицы А нашего примера вполне можно было бы использовать и строчное представление, полное, но ''неупорядоченное'' '''(RR (С) U )'''.

Неупорядоченное представление <math>A</math>:

IA = [ 1 4 4 6 ]
JA = [ 8 3 4 8 6 ]
AN = [ 5 1 3 1 7 ]

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

=== Умножение разреженной матрицы на вектор ===

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрицы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''';

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время его работы, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Основу алгоритма составляет вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB \le IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

Псевдокод алгоритма:

FOR I = 1, N (1)
U = 0. (2)
IAA = IA(I) (3)
IAB = IA(I + 1 ) - 1 (4)
IF NOT(IAB.LT.IAA) (5)
FOR J = IAA, IAB (6)
C(I) = U + AN(J)*B(JA(J)) (7)

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

Для всего алгоритма потребуется выполнить <math>O(k)</math> операций, как в строке стр.7 псевдокода алгоритма ([[#Схема реализации последовательного алгоритма|п.1.5]]), где <math>k</math> - число ненулевых элементов матрицы.

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

[[file:InfoGrafMatrixRRCUandVextor.jpg|thumb|center|1200px|Рисунок 1. Информационный граф алгоритма.]]

По оси <math>X</math> для отдельной строки <math>I</math> матрицы отложены в пределах первой <math>IAA</math> и последней <math>IAB</math> позиций ненулевых элементов значения <math>AN</math> и соответствуюие им по столбцовомым индексам, хранимимым в <math>JA</math>, значения <math>B</math> элементов.
Пары этих значений обозначены желтыми квадратиками <math>(in)</math>. Значения in попарно скалярно перемножаются (зеленый кружочек) и суммируются (синий кружочек) в результат значения элемента вектора-произведения <math>c_{i}</math>, т.е <math>out</math>(красный квадратик) с строковым индексом, соответствующем номеру строки матрицы.

По оси <math>Y</math> отложена схема вычисление значения каждого элемента вектора-произведения для каждой строки матрицы.

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

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

* <math>IA, JA, AN</math> - заданная матрица в форме '''(RR (С) U)''' c <math>k</math> ненулевыми элементами и <math>N</math> строками, <math>m</math> столбцами;

* <math>B</math> - заданный заполненный вектор c <math>m</math> элементами;
'''
'''Объем входных данных''': <math>k + m</math>

'''Выходные данные:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Объем выходных данных''': <math>N</math>

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

[1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T16:39:43Z

Lexaloris:

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T14:59:37Z

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

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T14:59:04Z

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

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T14:58:38Z

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

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T14:57:38Z

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

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T14:55:13Z

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

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T14:51:46Z

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

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T14:23:10Z

Lexaloris:

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T14:22:12Z

Lexaloris:

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T13:53:30Z

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

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T13:48:25Z

Lexaloris:

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T13:19:48Z

Lexaloris: /* Хранение ненулевых элементов разреженной матрицы */

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T13:07:28Z

Lexaloris: /* Хранение ненулевых элементов разреженной матрицы */

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T13:07:05Z

Lexaloris: /* Свойства и структура алгоритмов */

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T12:41:35Z

Lexaloris:

Участник:Kochet

2016-10-15T12:37:08Z

Lexaloris: Новая страница: «Кочетков Павел Александрович Группа 621.»

Кочетков Павел Александрович Группа 621.

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T05:21:12Z

Lexaloris: /* Литература */

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T05:19:01Z

Lexaloris:

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T05:05:03Z

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

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрийы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время работы алгоритма, является вычисление значения <math>i</math>-го элемента <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

[[File:InfoGrafMatrixRRCUandVextor.jpg]]

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T05:03:10Z

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

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрийы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время работы алгоритма, является вычисление значения <math>c_{i}</math> вектора-произведения, т.е произведения строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

[[File:InfoGrafMatrixRRCUandVextor.jpg]]

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T04:59:17Z

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

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрийы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

Вычислительным ядром, т.е. той частью алгоритма, на которую приходится основное время работы алгоритма, является вычисление скалярное произведение строки <math>I</math> матрицы <math>A</math> и вектора <math>B</math> по формуле:

:<math>
\begin{align}
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

[[File:InfoGrafMatrixRRCUandVextor.jpg]]

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T04:37:49Z

Lexaloris: /* Информационный граф */

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрийы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

[[File:InfoGrafMatrixRRCUandVextor.jpg]]

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T04:37:38Z

Lexaloris: /* Информационный граф */

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрийы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

[[File:InfoGrafMatrixRRCUandVextor.jpg]]
[[Файл:InfoGrafMatrixRRCUandVextor.jpg]]

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-15T04:34:24Z

Lexaloris: /* Информационный граф */

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрийы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

[[Файл:InfoGrafMatrixRRCUandVextor.jpg]]

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris

2016-10-15T04:31:35Z

Lexaloris: Новая страница: «Новоселов Алексей Дмитриевич. Студент МГУ ВМК. Группа 621.»

Новоселов Алексей Дмитриевич. Студент МГУ ВМК. Группа 621.

Обсуждение участника:Lineprinter

2016-10-15T04:30:15Z

Lexaloris: /* Перенос */

== Перенос ==
Статья: [[Участники: Бобошко А., Юмакаева А./Решение начальной задачи Коши для системы ОДУ методом Рунге-Кутта 4-го порядка]];
Выполняют: Бобошко Алексей и Юмакаева Алина

Статья: [[Алгоритм кластеризации, основанный на сетях Кохоннена]];
Выполняют: Логвиненко Александра и Адиев Тохтар

Статья: [[Ортогонализация Грама-Шмидта]];
Выполняют: [[Участник:KibAndrey| Кибанов Андрей]] и Аджиева Татьяна

Статья: [[Самоорганизующиеся карты Кохонена]];
Выполняет: [[Участник:Anton goy| Гой Антон]]

Статья:[[ЕМ-алгоритм_(Тематическое_моделирование)]];
Выполняют: Мурат Апишев и Андрей Заночкин

Статья:[[Алгоритм_Ланцоша_с_полной_переортогонализацией]];
Выполняет:[[Участник:Sfedotov| Федотов С.А.]]

Статья: [[Алгоритм_k-средних]]
Выполняют: [[Участник:Error2407|Богомазов Евгений]], [[Участник:Илья_Егоров|Егоров Илья]]

Статья: [[Нечеткий_алгоритм_С_средних]]
Выполняют: [[Участник:Demon smd|Д.А.Гуськов]], [[Участник:marina abramenkova|М.А.Абраменкова]]

Статья: [[Решение_задачи_Коши_для_системы_ОДУ_методом_Рунге-Кутты_4_порядка]];
Выполняют: [[Участник:Алимов_Дамир_Алиевич|Алимов Дамир]] и [[Участник:Anlesnichiy|Антон Лесничий]]

Статья: [[Строгий_алгоритм_С_средних_(Hard_C-Means,_HCM)]];
Выполняют: [[Участник:Светлана_Лукьяненко|Лукьяненко Светлана]] и [[Участник:Юрий_Комаров|Комаров Юрий]]

Статья: [[Алгоритм кластеризации, основанный на минимальном остовном дереве]];
Выполняет: [[Участник:Astandrik | Стандрик Антон Сергеевич]]

Статья: [[Умножение разреженной матрицы на вектор]];
Выполняет: [[Участник:Lexaloris | Новоселов Алексей]], Выполняет: [[Участник:pahom | Кочетков Павел]]

Статья: [[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(3)|Нахождение собственных чисел квадратной матрицы методом QR разложения (3)]];
Выполняют: [[Участник:Смирнова_Александра|Смирнова А.С.]], [[Участник:Александра_Киямова|Киямова А.]]

Статья: [[Метод_Якоби_вычисления_сингулярных_чисел_и_векторов]];
Выполняют: [[Участница:Почернина_Елена| Почернина Елена]] и [[Участница:Светлана|Костюкова Светлана]]

Статья: [[Метод_Ньютона_для_решения_систем_нелинейных_уравнений(2)]];
Выполняют: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений]];
Выполняют: [[Участник:Cookie|Шатков С.А.]], [[Антохина Ю.А.]]

Статья: [[Быстрое_преобразование_Фурье_(FFT)|Быстрое преобразование Фурье (FFT)]];
Выполняют: [[Участник:Victoria_Stepanischeva|Степанищева Виктория]] и [[Участник:Igor_Munkin|Мунькин Игорь]]

Статья: [[Быстрое_дискретное_преобразование_Фурье|Быстрое_дискретное_преобразование_Фурье]];
Выполняют: [[Участник:ivanov.kir.m | К.М.Иванов]], [[Участник:Pumpkin | А.C.Сапин]]

Статья:[[Алгоритм_k_средних]]
Выполняют: [[Участник:Parkhomenko|Пархоменко Павел]], [[Участник:ivan.mashonskiy|Машонский Иван]]

Статья:[[EM-алгоритм_кластеризации]]
Выполняет: [[Участник:Noite|Зинченко Дмитрий]]

Статья:[[Алгоритм_k_means]]
Выполняют: [[Участник:IanaV| Валуйская Яна]], [[Глотов Евгений]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы ЗП |Метод Якоби вычисления собственных значений симметричной матрицы ЗП]];
Выполняют: [[Участник:Зиновьев Владимир|Зиновьев В.С.]], [[Участник:Пронин Андрей|Пронин А.М.]]

Статья:[[Алгоритм_кластеризации,_основанный_на_минимальном_покрывающем_дереве]]
Выполняет: [[Участник:Kanast74|Дмитриева Анастасия]]

Статья:[[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(4)]]
Выполняют: [[Участник:F-morozov|Морозов Ф. В.]], [[Участник:Nataliya|Пащенко Н. Ф.]]

Статья:[[Хранение_ненулевых_элементов_разреженных_матриц._Умножение_разреженной_матрицы_на_вектор]];
Выполняют: [[Участник:Trrufina|Третьякова Р.М.]] и [[Участник:Екатерина_Буторина|Буторина Е.В.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений2]];
Выполняет: [[Участник:Лукьянова Анна|Лукьянова А.Я.]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы]];
Выполняют: [[Участник: Galkina|Галкина А.С.]], [[Участник: Игорь|Плахов И.А.]]

Статья: [[Метод рекурсивной координатной бисекции]];
Выполняют: [[Участник: Obirvalger|Гордеев Михаил]], [[Участник: KolmakovEA|Колмаков Евгений]]

Статья: [[Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок)]];
Выполняют: [[Участник: Эльвира Ахиярова|Ахиярова Эльвира]]

Статья: [[Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор]];
Выполняют: [[Участник: Janyell|Сычева Евгения]], [[Участник: Ahahalin|Хахалин Анатолий]]

Статья: [[Построение матрицы Адамара произвольного размера]];
Выполняют: [[Участник: Бугаков Юрий|Бугаков Юрий]], Кужамалиев Ернур

Статья: [[Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки (1)]]
Выполняют: [[Участница:Sannikovats| Санникова Татьяна Сергеевна]], [[Участник:Plukshin| Лукшин Петр Андреевич]]

Статья: [[Алгоритм кластеризации, основанный на построении каркаса]];
Выполняют: [[Участник:SenderovichNikita| Сендерович Никита]]

Статья: [[Алгоритм кластеризации, основанный на максимизации ожидания]];
Выполняют: Готман Мария, Лукашкина Юлия

Статья: [[Partitioning_Around_Medoids_(PAM)]]
Выполняют: [[Участник:Avasilenko|А.Э.Василенко]], [[Участник:Anastasia|А.В.Тузикова]]

Статья: [[Участник:Муромцев Н.А. и Дворецкий М.С ./ Нечеткий алгоритм С средних (Fuzzy C-means) (23)]]
Выполняют: [[Участник:Nikmedoed|Н.А. Муромцев]], Дворецкий Михаил Сергеевич

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-12T11:14:24Z

Lexaloris: /* Свойства алгоритма */

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрийы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-12T10:36:44Z

Lexaloris: /* Общее описание алгоритма */

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

Пусть <math>N</math> — число строк матрицы.
Для каждой ее строки <math>I</math> матрийы мы находим с помощью <math>IA</math> значения первой <math>IAA</math> и последней <math>IAB</math> позиций, занимаемых элементами строки <math>I</math> в массивах <math>JA</math> и <math>AN</math>. Затем, чтобы вычислить скалярное произведение строки <math>I</math> и вектора <math>B</math>, мы просто просматриваем <math>JA</math> и <math>AN</math> на отрезке от <math>IAA</math> до <math>IAB</math>:
каждое значение, хранимое в <math>JA</math>, есть столбцовый индекс и используется для извлечения из массива <math>B</math> элемента, который должен быть умножен на соответствующее число из <math>AN</math>. Результат каждого умножения прибавляется к <math>C(I)</math>.

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-12T10:30:13Z

Lexaloris: /* Общее описание алгоритма */

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

Пусть N — число строк матрицы. Если b — заполненный, то к его элементам, находящимся в В, доступ может быть произвольным.
Для каждой ее строки I матрицы мы находим с помощью IA значения первой IAA и последней IAB позиций, занимаемых элементами строки I в массивах JA и AN. Затем, чтобы вычислить скалярное произведение строки I и вектора В, мы просто просматриваем JA и AN на отрезке от IAA до IAB:
каждое значение, хранимое в JA, есть столбцовый индекс и используется для извлечения из массива В элемента, который должен бытьумножен на соответствующее число из AN. Результат каждого умножения прибавляется к С (I).

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-12T10:25:40Z

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

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

Для всего алгоритма потребуется выполнить <math>O(M)</math> операций, где <math>M</math> - число ненулевых элементов матрицы.

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

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>

Участник:Lexaloris/Умножение разреженной матрицы на вектор

2016-10-12T10:22:21Z

Lexaloris: /* Свойства алгоритма */

'''Авторы страницы:''' Кочетков П.А и Новоселов А.Д.

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

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

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

'''Исходные данные:'''

<math>IA, JA, AN</math> - заданная матрица в форме RR (С) U;

<math>B</math> - заданный заполненный вектор;

<math>N</math> - число строк матрицы.

'''Выход:''' <math>C</math> вектор-произведение размерности <math>N</math>.

'''Формулы метода:'''

:<math>
\begin{align}
& IAA_{i} = IA(i), \quad i \in [1, N], \\
& IAB_{i} = IA(i + 1) - 1, \quad i \in [1, N], \\
& c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j)), \quad i \in [1, N] \\
\end{align}
</math>

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

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

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

Последовательность исполнения метода следующая:

Далее для всех <math>i</math> от <math>1</math> до <math>N</math> по нарастанию выполняются:

1. <math> c_{i} = 0; IAA = IA(i); IAB = IA(i + 1 ) - 1 </math>

После этого, если <math>(IAB <= IAA)</math>:

2. Для всех <math>j</math> от <math>IAA</math> до <math>IAB</math> выполняется:

<math>c_{i} = \sum\limits_{j = IAA_{i}}^{IAB_{i}} AN(j)B(JA(j))</math>

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

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

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

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

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

Алгоритм в рамках выбранной версии полностью детерминирован.

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

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

= Литература =

<references \>