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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 31: Строка 31:
  
 
  '''Входные данные''':
 
  '''Входные данные''':
 +
  число строк матрицы ''n'';
 
   разреженная матрица в формате CSR:
 
   разреженная матрица в формате CSR:
     ''IA'', ''JA'' ''A'' с весами ''f''(''e'');
+
     строчные указатели ''IA'',
 +
    столбцовые указатели''JA'',
 +
    ненулевые элементы ''A'';
 
   вектор ''x''.
 
   вектор ''x''.
 
  '''Выходные данные''': произведение матрицы на вектор ''y''.
 
  '''Выходные данные''': произведение матрицы на вектор ''y''.
 
   
 
   
 
  ''Q'' := '''new''' priority queue
 
  ''Q'' := '''new''' priority queue
  '''for each''' ''v'' ∈ ''V'':
+
  '''for''' ''i'' = 1,n:
    '''if''' ''v'' = ''u'' '''then''' ''d''(''v'') := 0 '''else''' ''d''(''v'') := ∞
+
  '''for''' ''k'' = ''IA(i)'', ''IA(i+1)''-1:
    ''Q''.insert(''v'', ''d''(''v''))
+
            y(i) += A(k)*x(JA(k));
 
'''while''' ''Q'' ≠ ∅:
 
    ''v'' := ''Q''.delete_min()
 
    '''for each''' ''e'' = (''v'', ''w'') ∈ ''E'':
 
        '''if''' ''d''(''w'') > ''d''(''v'') + ''f''(''e''):
 
            ''d''(''w'') := ''d''(''v'') + ''f''(''e'')
 
            ''Q''.decrease_key(''w'', ''d''(''w''))
 
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===

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


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

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


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

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

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

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

Исходные данные: матрица [math]A[/math] (элементы [math]A_{ij}, i, j = 1, \ldots, n[/math]).,

вектор [math]b[/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.