Уровень алгоритма

Участник:Руфина Третьякова/Хранение ненулевых элементов разреженных матриц. Умножение разреженной матрицы на вектор: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
← Предыдущая правкаСледующая правка →
Строка 20: Строка 20:


=== Математическое описание алгоритма ===
=== Математическое описание алгоритма ===
Исходные данные:  матрица <math>A</math> (элементы <math>A_{ij}, i, j = 1, \ldots, n</math>).,
Исходные данные:  разреженная матрица <math>A^{n*n}</math>, вектор <math>b^{n*1}</math>  
вектор <math>b</math>  


Вычисляемые данные: вектор  <math>c</math>
Рассмотрим CSR-представление разреженных матриц
 
CSR-формат представляет матрицу {{math|'''M'''}} в виде 3-х одномерных массивов:
 
массив <math>A</math> содержит ненулевые значения матрицы,
<math>JA</math> - номера столбцов ненулевых элементов.,
<math>IA</math>- содержит номер с которого начинается описание элементов в массивах,
Этот формат позволяет быстро производить р=перемножение матрицы на вектор ({{math|'''M'''''x''}}).
 
The CSR format stores a sparse {{math|''m'' × ''n''}} matrix {{math|'''M'''}} in row form using three (one-dimensional) arrays {{math|(A, IA, JA)}}.  Let {{math|NNZ}} denote the number of nonzero entries in {{math|'''M'''}}.  (Note that [[Zero-based numbering|zero-based indices]] shall be used here.)
 
* The array {{math|A}} is of length {{math|NNZ}} and holds all the nonzero entries of {{math|'''M'''}} in left-to-right top-to-bottom ("row-major") order.
* The array {{math|IA}} is of length {{math|''m'' + 1}}.  It is defined by this recursive definition:
** {{math|IA[0] {{=}} 0}}
** {{math|IA[''i''] {{=}} IA[''i'' − 1] +}} (number of nonzero elements on the {{math|(''i'' − 1)}}-th row in the original matrix)
** Thus, the first {{math|''m''}} elements of {{math|IA}} store the index into {{math|A}} of the first nonzero element in each row of {{math|'''M'''}}, and the last element {{math|IA[''m'']}} stores {{math|NNZ}}, the number of elements in {{math|A}}, which can be also thought of as the index in {{math|A}} of first element of a phantom row just beyond the end of the matrix {{math|'''M'''}}.  The values of the {{math|''i''}}-th row of the original matrix is read from the elements {{math|A[IA[''i''<nowiki>]]</nowiki>}} to {{math|A[IA[''i'' + 1] − 1]}} (inclusive on both ends), i.e. from the start of one row to the last index just before the start of the next.<ref>[http://netlib.org/linalg/html_templates/node91.html netlib.org]</ref>
* The third array, {{math|JA}}, contains the column index in {{math|'''M'''}} of each element of {{math|A}} and hence is of length {{math|NNZ}} as well.
 
 
Например, матрица
:: <math>\begin{pmatrix}
0 & 0 & 0 & 0 \\
5 & 8 & 0 & 0 \\
0 & 0 & 3 & 0 \\
0 & 6 & 0 & 0 \\
\end{pmatrix}</math>
 
это {{math|4 × 4}} разреженная матрица с 4-мя ненулевыми элементами, представляемая в формате CSR
 
    A  = [ 5 8 3 6 ]
    IA = [ 0 0 2 3 4 ]
    JA = [ 0 1 2 1 ]
где вектор
 
Вычисляемые данные: вектор  <math>c^{n*1}</math>


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

Версия от 21:14, 12 октября 2016


Умножение разреженной матрицы на вектор
Последовательный алгоритм
Последовательная сложность [math]\displaystyle{ }[/math]
Объём входных данных [math]\displaystyle{ }[/math]
Объём выходных данных [math]\displaystyle{ }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]\displaystyle{ }[/math]
Ширина ярусно-параллельной формы [math]\displaystyle{ }[/math]

Авторы статьи: Третьякова Р. М. (группа 603), Буторина Е. В. (группа 603)


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

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

Разрежённая матрица — это матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевые, матрица считается плотной. Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных. При хранении и преобразовании разрежённых матриц в компьютере бывает полезно, а часто и необходимо, использовать специальные алгоритмы и структуры данных, которые учитывают разрежённую структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно к большим разрежённым матрицам работают относительно медленно и требуют значительных объёмов памяти. Однако разрежённые матрицы могут быть легко сжаты путём записи только своих ненулевых элементов, что снижает требования к компьютерной памяти.

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

Исходные данные: разреженная матрица [math]\displaystyle{ A^{n*n} }[/math], вектор [math]\displaystyle{ b^{n*1} }[/math]

Рассмотрим CSR-представление разреженных матриц

CSR-формат представляет матрицу Шаблон:Math в виде 3-х одномерных массивов:

массив [math]\displaystyle{ A }[/math] содержит ненулевые значения матрицы, [math]\displaystyle{ JA }[/math] - номера столбцов ненулевых элементов., [math]\displaystyle{ IA }[/math]- содержит номер с которого начинается описание элементов в массивах, Этот формат позволяет быстро производить р=перемножение матрицы на вектор (Шаблон:Math).

The CSR format stores a sparse Шаблон:Math matrix Шаблон:Math in row form using three (one-dimensional) arrays Шаблон:Math. Let Шаблон:Math denote the number of nonzero entries in Шаблон:Math. (Note that zero-based indices shall be used here.)


Например, матрица

[math]\displaystyle{ \begin{pmatrix} 0 & 0 & 0 & 0 \\ 5 & 8 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 6 & 0 & 0 \\ \end{pmatrix} }[/math]

это Шаблон:Math разреженная матрица с 4-мя ненулевыми элементами, представляемая в формате CSR 

   A  = [ 5 8 3 6 ]
   IA = [ 0 0 2 3 4 ]
   JA = [ 0 1 2 1 ]

где вектор

Вычисляемые данные: вектор [math]\displaystyle{ c^{n*1} }[/math]

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

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

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

Входные данные:
 число строк матрицы n; 
 разреженная матрица в формате CSR:
   строчные указатели IA,
   столбцовые указателиJA, 
   ненулевые элементы A;
 вектор x.
Выходные данные: произведение матрицы на вектор y.

Q := new priority queue
for i = 1,n:
 for k = IA(i), IA(i+1)-1:
           y(i) += A(k)*x(JA(k));

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

Метод можно описать следующим образом:


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

Для вычисления сингулярных чисел и векторов матрицы порядка n в последовательном варианте требуется:

  • [math]\displaystyle{ }[/math] делений,
  • [math]\displaystyle{ }[/math] сложений (вычитаний),
  • [math]\displaystyle{ }[/math] умножений.

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

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

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

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

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

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

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

Литература

1. С. Писсанецки Технология разреженных матриц. Изд. Мир, 1988.

  1. ↑ netlib.org
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Участник:Руфина_Третьякова/Хранение_ненулевых_элементов_разреженных_матриц._Умножение_разреженной_матрицы_на_вектор&oldid=6102