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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 20: Строка 20:
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Исходные данные:  разреженная матрица <math>A^{n*n}</math>, вектор <math>b^{n*1}</math>  
+
Исходные данные:  разреженная матрица <math>M^{n*n}</math>, вектор <math>x^{n*1}</math>  
  
 
Рассмотрим CSR-представление разреженных матриц
 
Рассмотрим CSR-представление разреженных матриц
  
CSR-формат представляет матрицу {{math|'''M'''}} в виде 3-х одномерных массивов:
+
CSR-формат представляет матрицу <math>M</math> в виде 3-х одномерных массивов:
  
 
массив <math>A</math> содержит ненулевые значения матрицы,
 
массив <math>A</math> содержит ненулевые значения матрицы,
 
<math>JA</math> - номера столбцов ненулевых элементов.,  
 
<math>JA</math> - номера столбцов ненулевых элементов.,  
 
<math>IA</math>- содержит номер с которого начинается описание элементов в массивах,  
 
<math>IA</math>- содержит номер с которого начинается описание элементов в массивах,  
Этот формат позволяет быстро производить р=перемножение матрицы на вектор ({{math|'''M'''''x''}}).  
+
Этот формат позволяет быстро производить перемножение матрицы <math>M</math> на вектор <math>x</math>.  
  
  
Строка 46: Строка 46:
 
     IA = [ 0 0 2 3 4 ]
 
     IA = [ 0 0 2 3 4 ]
 
     JA = [ 0 1 2 1 ]
 
     JA = [ 0 1 2 1 ]
где вектор
 
  
Вычисляемые данные: вектор  <math>c^{n*1}</math>
+
 
 +
Вычисляемые данные: вектор  <math>M*x</math>=<math>c</math>
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===

Версия 00:20, 13 октября 2016


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

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


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

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

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

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

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

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

CSR-формат представляет матрицу [math]M[/math] в виде 3-х одномерных массивов:

массив [math]A[/math] содержит ненулевые значения матрицы, [math]JA[/math] - номера столбцов ненулевых элементов., [math]IA[/math]- содержит номер с которого начинается описание элементов в массивах, Этот формат позволяет быстро производить перемножение матрицы [math]M[/math] на вектор [math]x[/math].


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

[math]\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]M*x[/math]=[math]c[/math]

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

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

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

Входные данные:
 число строк матрицы 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));

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

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


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

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

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

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

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

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

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

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

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

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

3 Литература

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