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

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

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

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

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

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

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

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

вектор [math]\displaystyle{ b }[/math] 

Вычисляемые данные: вектор [math]\displaystyle{ c }[/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.